JS数组去重的n种解法

已知排序的array，或者不在乎去重之后的结果顺序

Solution 1
可以做一次循环，判断当前的item是否等于前面那个item，如果不等于或不存在前面的item，就push到result中。
时间复杂度：O(nlogn)
空间复杂度：O(n)

Array.prototype.uniq = function () {
    if (!this.length || this.length == 0) return this;
    this.sort();
    var res = [this[0]];
    for (var i = 1; i < this.length; i++) {
        if (this[i] != this[i - 1]) res.push(this[i]);
    }
    return res;
}

Solution 2
采用两个指针l和r，记录不重复元素的位置，r从l的下一个开始遍历数组，如果r位置的数字等于l位置的数字，说明该数字重复出现，不予处理；如果r位置的数字不等于l位置的数字，说明该数字没有重复，需要放到l的下一位置，并使l加1.
时间复杂度：O(nlogn)
空间复杂度：O(1)

Array.prototype.uniq = function () {
    if (!this.length || this.length == 0) return this;
    this.sort();
    var left = 0, right;
    for (right = left + 1; right < this.length; right++) {
        if (this[left] != this[right]) {
            this[++left] = this[right];
        }
    }
    return this.slice(0, left + 1);
}

Solution 3
数组先排序，比较俩数组一头一尾进行去重。

Array.prototype.uniq = function () {
    var res = [], end;
    this.sort();
    end = this[0], res.push(this[0]);
    for (var i = 1; i < this.length; i++) {
        if (this[i] != end) {
            res.push(this[i]);
            end = this[i];
        }
    }
    return res;
}

如果数组顺序杂乱

Solution 1
可以做一次循环，用一个对象标记该item是否存在。如果不存在，就push到result中。这里使用一个hashtable的结构记录已有的元素，这样就可以避免内层循环。不过，假如数组非常庞大，这种做法的性能会差。

Array.prototype.uniq = function () {
    var hash = {}, result = [], item;
    for (var i = 0; i < this.length; i++) {
        item = this[i]; 
        var key = Object.prototype.toString.call(item) + item;
        if (!hash[key]) {
            hash[key] = true;
            result.push(item);
        }
    }
    return result;
}

注意js中hash的键值是以字符存储的，所以会自动将数组元素转为字符型，因此作为hash索引时需要加上类型，否则无法区分数字1和字符1。
Solution 2
遍历数组，建立新数组，利用indexOf判断是否存在于新数组中，不存在则push到新数组，最后返回新数组。时间复杂度为O(n^2)。

Array.prototype.uniq = function () {
    var ret = [];
    for (var i = 0; i < this.length; i++) {
        if (ret.indexOf(this[i]) == -1) {
            ret.push(arr[i]);
        }
    }
    return ret;
}

Solution 3
遍历数组，利用object对象保存数组值，判断数组值是否已经保存在object中，未保存则push到新数组并用object[arrayItem] = 1的方式记录保存。

Array.prototype.uniq = function () {
    var ret = [], tmp = [];
    for (var i = 0; i < this.length; i++) {
        if (!tmp[arr[i]]) {
            tmp[arr[i]] = 1;
            ret.push(arr[i]);
        }
    }
    return ret;
}

Solution 4
数组下标判断法。遍历数组。利用indexOf判断元素的值是否与当前元素索引相等，如相等则加入。

Array.prototype.uniq = function () {
    var res = [];
    var me = this;
    me.forEach(function (val, index) {
        if (me.indexOf(val) == index) 
           res.push(val);
    })
    return res;
}

可以用filter过滤。

Array.prototype.uniq = function () {
    var me = this;
    var res = me.filter(function (x, index) {
        return me.indexOf(x) == index;
    }); 
    return res;
}

Solution 5
将原数组中重复元素的最后一个元素放入结果数组中。

Array.prototype.uniq = function () {
    var res = [];
    for (var i = 0; i < this.length; i++) {
        for (var j = i + 1; j < this.length; j++) {
            if (this[i] == this[j]) j = ++i;
        }
        res.push(this[i]);
    }
    return res;
}

ES6

function unique(arr) {
  return Array,from(new Set(arr));
}