JavaScript基础部分

算法题：有一个长度为n一1的数组，包含1一n中不重复的乱序的数，求寻找范围内不在数组中的数，考虑空间占用，性能优化，溢出等情况，至少写两个算法

当n不太大时，可以考虑求和。先算出1~n的所有数的和，然后减去数组中出现的所有自然数的和。时间复杂度为O(n)，空间复杂度O(1)。这种方法的缺点是n不能太大，n比较大时，求和容易溢出。

用位图。从头到尾的扫描整个数组，把出现的数相应的位设置为1.然后再扫描位图，找出不为1的那一位，即为要找的数。这种方法的时间复杂度为O(n),空间复杂度为O(n)。

异或有个很巧妙的地方：同一变量和该变量与另一变量的异或值的异或等于这个变量自身。所以我们可以把1~n的所有数异或，再把数组中出现的所有数异或，然后再把这两个异或的结果异或，最后得到的值即为我们要找的值。这样时间复杂度为O(n),空间复杂度为O（1）。在空间上比第二种方法要好，而且不会出现第一种方法中所说的溢出问题

实现以下方法（与标准一致）

Element.prototype.getElementsByClassName：

Element.prototype.getElementsByClassName = function(searchClass, node, tag) {
    if (document.getElementsByClassName) {
        var nodes = (node || document).getElementsByClassName(searchClass), 
            result = [];
        for (var i = 0; node = nodes[i++]; ) {
            if (tag !== "*" && node.tagName === tag.toUpperCase()) {
                result.push(node);
            }
        }
        return result;
    } else {
        node = node || document;
        tag = tag || "*";
        var classes = searchClass.split(" "), 
            elements = (tag === "*" && node.all) ? node.all : node.getElementsByTagName(tag), 
            patterns = [], 
            current, 
            match;
        var i = classes.length;
        while (一一i >= 0) {
            patterns.push(new RegExp("(^|\s)" + classes[i] + "(\s|$)"));
        }
        var j = elements.length;
        while (一一j >= 0) {
            current = elements[j];
            match = false;
            for (var k = 0, kl = patterns.length; k < kl; k++) {
                match = patterns[k].test(current.className);
                if (!match)
                    break;
            }
            if (match)
                result.push(current);
        }
        return result;
    }
}

View Code

Function.prototype.bind：

Function.prototype.bind = function (oThis) {
    if (typeof this !== "function") {
        throw new TypeError("bind function error");
    }
    var aArgs = Array.prototype.slice.call(arguments,1),
        fToBind = this, 
        fBound = function () {
            return fToBind.apply(oThis || window,aArgs.concat(Array.prototype.slice.call(arguments)));
        };
    return fBound;
};

View Code

编写一个方法去掉一个数组的重复元素

1.遍历数组法

最简单的去重方法，实现思路：新建一新数组，遍历传入数组，值不在新数组就加入该新数组中；注意点：判断值是否在数组的方法“indexOf”是ECMAScript5 方法，IE8以下不支持，需多写一些兼容低版本浏览器代码，源码如下：

// 最简单数组去重法
function unique1(array){
  var n = [ ]; //一个新的临时数组
  //遍历当前数组
  for(var i = 0; i < array.length; i++){
    //如果当前数组的第i已经保存进了临时数组，那么跳过，
    //否则把当前项push到临时数组里面
    if (n.indexOf(array[i]) == 一1) n.push(array[i]);
  }
  return n;
}
// 判断浏览器是否支持indexOf ，indexOf 为ecmaScript5新方法 IE8以下（包括IE8， IE8只支持部分ecma5）不支持
if (!Array.prototype.indexOf){
  // 新增indexOf方法
  Array.prototype.indexOf = function(item){
    var result = 一1, a_item = null;
    if (this.length == 0){
      return result;
    }
    for(var i = 0, len = this.length; i < len; i++){
      a_item = this[i];
      if (a_item === item){
        result = i;
        break;
      }  
    }
    return result;
  }
}

View Code

2.对象键值对法

该方法执行的速度比其他任何方法都快，就是占用的内存大一些；实现思路：新建一js对象以及新数组，遍历传入数组时，判断值是否为js对象的键，不是的话给对象新增该键并放入新数组。注意点：判断是否为js对象键时，会自动对传入的键执行“toString()”，不同的键可能会被误认为一样；例如： a[1]、a["1"] 。解决上述问题还是得调用“indexOf”。

// 速度最快， 占空间最多（空间换时间）
function unique2(array){
  var n = {}, r = [], len = array.length, val, type;
    for (var i = 0; i < array.length; i++) {
        val = array[i];
        type = typeof val;
        if (!n[val]) {
            n[val] = [type];
            r.push(val);
        } else if (n[val].indexOf(type) < 0) {
            n[val].push(type);
            r.push(val);
        }
    }
    return r;
}

View Code

3.数组下标判断法

还是得调用“indexOf”性能跟方法1差不多，实现思路：如果当前数组的第i项在当前数组中第一次出现的位置不是i，那么表示第i项是重复的，忽略掉。否则存入结果数组。

function unique3(array){
  var n = [array[0]]; //结果数组
  //从第二项开始遍历
  for(var i = 1; i < array.length; i++) {
    //如果当前数组的第i项在当前数组中第一次出现的位置不是i，
    //那么表示第i项是重复的，忽略掉。否则存入结果数组
    if (array.indexOf(array[i]) == i) n.push(array[i]);
  }
  return n;
}

View Code

4.排序后相邻去除法

虽然原生数组的”sort”方法排序结果不怎么靠谱，但在不注重顺序的去重里该缺点毫无影响。实现思路：给传入数组排序，排序后相同值相邻，然后遍历时新数组只加入不与前一值重复的值。

// 将相同的值相邻，然后遍历去除重复值
function unique4(array){
  array.sort(); 
  var re=[array[0]];
  for(var i = 1; i < array.length; i++){
    if( array[i] !== re[re.length一1])
    {
      re.push(array[i]);
    }
  }
  return re;
}

View Code

5.优化遍历数组法

实现思路：获取没重复的最右一值放入新数组。（检测到有重复值时终止当前循环同时进入顶层循环的下一轮判断）

// 思路：获取没重复的最右一值放入新数组
function unique5(array){
  var r = [];
  for(var i = 0, l = array.length; i < l; i++) {
    for(var j = i + 1; j < l; j++)
      if (array[i] === array[j]) j = ++i;
    r.push(array[i]);
  }
  return r;
}

View Code

6.利用es5中的方法，简化上述操作

function unique6(array){
    var hash = {}
    var res = []
    array.map(function(value,index,arr){
        if(!hash[value]){
            hash[value] = 1
            res.push(value)
        }
    })
    return res 
}

View Code

function unique7(array){
    var hash = {}
    var res = array.filter(function(value,index,arr){
        if(!hash[value]){
            hash[value] = 1
            return true
        }
        return false
    })
    return res  
}

View Code

7.利用es6中Set对象及展开操作符...

function unique7(array){
    var tmp = new Set(array)
    var res = [...tmp]
    return res  
}

请使用javascript写出数组快速排序代码

快速排序的思想:分治，每次从选取索引的中间值将数组分为大于或小于该值的两部分，重复操作，直至最后的值为空或只有一个值

function quiktSort(arr){
        var  left =[],right=[];
        if(arr.length<1){
            return  arr;
        }
        var  index = Math.floor(arr.length/2);
        var  point = arr.splice(index,1);
        for(var i=0,len=arr.length;i<len;i++){
            if(arr[i]<point){
        left.push(arr[i]);
}else{
    right.push(arr[i]);
}
        }
        return quickSort(left).concat(point,quickSort(right));
    }

View Code