怎么以O(n)的复杂度实现数组的去重？（js）

Question

问题描述：

如何以 `O(n)` 的时间复杂度实现字符序列的去重，如对以下数组去重

[1, 'a', '1', 2, '2', 'b', 'b', null, null, , ,'null']

1 和 ‘1’不算重复，undefined， null 也要保留。不使用ES6的语法。

Answer 1

var arr = [1, 'a', '1', 2, '2', 'b', 'b'];
let resultarr = [...new Set(arr)]; 
console.log(resultarr);//[1, "a", "1", 2, "2", "b"]

如果不去重对象的可以用下面的

var arr = [1, 'a', '1', 2, '2', 'b', 'b', null, null, , ,'null'];
var obj = {};
var result = [];

for (var i = 0; i < arr.length; i++) {
  var key = typeof arr[i]+arr[i];
   if(!obj[key]){
     obj[key] = true;
     result.push(arr[i])
   }
}
console.log(result);

//或者不用多余的数组存储
for (var i = 0; i < arr.length; i++) {
  var key = typeof arr[i]+arr[i];
   if(!obj.hasOwnProperty(key)){
     obj[key] = arr[i];
   }
}

console.log(Object.values(obj));//es5 for in遍历

Answer 2

可以放在桶里

var arr = [1, 'a', '1', 2, '2', 'b', 'b'];
var obj = {};

for (var i = 0; i < arr.length; ++i) {
   obj[arr[i]] = 1;  
}

Object.keys(obj);

复杂度：O(2n)，一般约定数字是可以忽略的，即 O(n)

Answer 3

遍历（O(n)，使用一个哈希表（O(1)）来判断是否重复

Answer 4

Map Set(可以直接去重) Object(无法区分数字和字符串)
本质是在hashmap中判断key是否存在的的时间复杂度是O(1)

Answer 5

判断全等不可以么？楼上已经提供es6

var arr = [1, 'a', '1', 2, '2', 'b', 'b']
arr.sort();
for(var i = 0 ;i <arr.length;i++){
    for(var j = i+1;j<arr.length;j++){
        arr[i]===arr[j] ? arr.splice(i,1) :''
    }
}