数组去重

Posted on | In ,

循环（O(n^2)）

普通对比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function unique (arr) {
  var ans = []
  for (var i = 0; i < arr.length; i ++) {
    for (var j = 0; j < ans.length; j ++) {
      if (arr[i] === ans[j]) {
        break
      }
    }
    if (j == ans.length) {
      ans.push(arr[i])
    }
  }
  return ans
}
var a = [1, 1, 3, 2, 1, 2, 4, '1', {}, {}]
var ans = unique(a)
console.log(ans) // [ 1, 3, 2, 4, '1', {}, {} ]

使用indexOf

1
2
3
4
5
6
7
8
9
10
11
12
function unique (arr) {
  var ans = []
  for (var i = 0; i < arr.length; i ++) {
    if (ans.indexOf(arr[i]) == -1) {
      ans.push(arr[i])
    }
  }
  return ans
}
var a = [1, 1, 3, 2, 1, 2, 4, '1', {}, {}]
var ans = unique(a)
console.log(ans) // [ 1, 3, 2, 4, '1', {}, {} ]

先排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function unique (arr) {
  var sortedArr = arr.sort(),
    ans = []
  ans.push(sortedArr[0])
  for (var i = 1; i < sortedArr.length; i ++) {
    if (sortedArr[i] !== sortedArr[i - 1]) {
      ans.push(sortedArr[i])
    }
  }
  return ans
}
var a = [1, 1, 3, 2, 1, 2, 4, '1', {}, {}]
var ans = unique(a)
console.log(ans) // [ 1, '1', 2, 3, 4, {}, {} ]

利用filter方法

1
2
3
4
5
6
7
8
function unique (arr) {
  return arr.sort().filter(function (item, index, arr) {
    return !index || arr[index] !== arr[index - 1]
  })
}
var a = [1, 1, 3, 2, 1, 2, [], 4, '1', {}, {}, 3, []]
var ans = unique(a)
console.log(ans) // [ [], [], 1, '1', 2, 3, 4, {}, {} ]

建立对应表

把对象作为对应表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function unique (arr) {
  var obj = {}
  return arr.filter(function (item, index, arr) {
    var key = typeof(item) + item
    // [] -> object
    // {} -> object[object Object]
    // new String(1) -> object1
    // new Number(1) -> object1
    // {name: 'wangyi'} ->object[object Object]
    // new Object() -> object[object Object]
    // new Object(1) -> object1 等同于直接调用基本包装类型
    console.log(key)
    return obj[key] ? false : obj[key] = true
  })
  console.log(obj)
}
var test = []
var a = [1, 1, 3, 2, 1, 2, test, test, 4, '1', {}, {}, 3, test, new String('a'), {name: "wangyi"}, {age: 30}, new String(1), new Number(1)]
var ans = unique(a)
console.log(ans) // [ 1, 3, 2, [], 4, '1', {}, [String: 'a'], [String: '1'] ]

不给key加类型则无法区分’1’和1，且无法区分引用类型，给key加类型可以区分’1’和1，仍旧无法区分引用类型值。

建立Map数据类型的对应表

1
2
3
4
5
6
7
8
9
10
function unique (arr) {
  var map = new Map()
  return arr.filter(function (item, index, arr) {
    return map.get(item) ? false : map.set(item, true)
  })
}
var test = []
var a = [1, 1, 3, 2, 1, 2, test, test, 4, '1', {}, {}, 3, test, new String('a'), {name: "siren"}, {age: 30}, new String(1), new Number(1)]
var ans = unique(a)
console.log(ans) // [ 1, 3, 2, [], 4, '1', {}, {}, [String: 'a'], { name: 'siren' }, { age: 30 }, [String: '1'], [Number: 1] ]

利用map代替对象建立对应关系表，解决key混淆的问题。

ES6的Set数据类型

1
2
3
4
5
6
7
function unique (arr) {
  return Array.from(new Set(arr))
}
var test = []
var a = [1, 1, 3, 2, 1, 2, test, test, 4, '1', {}, {}, 3, test, new String('a'), {name: "siren"}, {age: 30}, new String(1), new Number(1)]
var ans = unique(a)
console.log(ans) // [ 1, 3, 2, [], 4, '1', {}, {}, [String: 'a'], { name: 'siren' }, { age: 30 }, [String: '1'], [Number: 1] ]