js前端面试题及答案整理（一）

Part1 手写代码

现场手写代码是现在面试中很常见的一类面试题，考察基础的数据结构与算法能力。

1 数组去重的实现
基本数组去重

Array.prototype.unique = function(){ var result = []; this.forEach(function(v){  if(result.indexOf(v) < 0){   result.push(v);  } }); return result;}

•利用hash表去重，这是一种空间换时间的方法

Array.prototype.unique = function(){ var result = [],hash = {}; this.forEach(function(v){  if(!hash[v]){   hash[v] = true;   result.push(v);  } }); return result;}

上面的方法存在一个bug，对于数组[1,2,'1','2',3]，去重结果为[1,2,3]，原因在于对象对属性索引时会进行强制类型转换，arr[‘1']和arr[1]得到的都是arr[1]的值，因此需做一些改变：

Array.prototype.unique = function(){ var result = [],hash = {}; this.forEach(function(v){  var type = typeof(v); //获取元素类型  hash[v] || (hash[v] = new Array());  if(hash[v].indexOf(type) < 0){   hash[v].push(type); //存储类型   result.push(v);  } }); return result;}

•先排序后去重

Array.prototype.unique = function(){ var result = [this[0]]; this.sort(); this.forEach(function(v){  v != result[result.length - 1] && result.push(v); //仅与result最后一个元素比较 });}

2 快速排序的实现

方法一(尽可能不用js数组方法）：

function quickSort(arr){ qSort(arr,0,arr.length - 1);}function qSort(arr,low,high){ if(low < high){  var partKey = partition(arr,low,high);  qSort(arr,low, partKey - 1);  qSort(arr,partKey + 1,high); }}function partition(arr,low,high){ var key = arr[low]; //使用第一个元素作为分类依据 while(low < high){  while(low < high && arr[high] >= arr[key])   high--;  arr[low] = arr[high];  while(low < high && arr[low] <= arr[key])   low++;  arr[high] = arr[low]; } arr[low] = key; return low;}

方法二（使用js数组方法）：

function quickSort(arr){ if(arr.length <= 1) return arr; var index = Math.floor(arr.length/2); var key = arr.splice(index,1)[0]; var left = [],right = []; arr.forEach(function(v){  v <= key ? left.push(v) : right.push(v); }); return quickSort(left).concat([key],quickSort(right));}

另外要知道，快速排序的平均时间复杂度O(nlogn),最坏情况是有序的情况，时间复杂度为n的平方，另外快速排序是不稳定的。

Part2 JavaScript相关

1 JavaScript基础数据类型

JavaScript数据类型包括原始类型和引用类型，原始类型有五个:
  Number（数值） String（字符串） Boolean（布尔） Null（空） Undefined（未定义）

引用类型有一个：
 Object（对象）

通过typeof(x)可以返回一个变量x的数据类型“number”、“string”、“boolean”、“undefined”、"object"，这里要注意一点：typeof运算符对于null类型返回的是object。