数组去重的方法整理

Share

只做各方神仙的搬运工

一、最笨的方法

  • 以下方法是基础的方法，但是时间复杂度为O(n2),性能很差。不过相较于其他方法，兼容性很好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function single(origin) {
	var result = [];
	var arrayItem, resultItem
	for(var i=0; i<origin.length; i++){
		 arrayItem = origin[i]
		for(var j=0; j<result.length; j++){
			 resultItem = result[j]
			if(resultItem === arrayItem){
			break;
		  }
		}
		if( j === result.length) {
			result.push(arrayItem)
		}
	}
}

二、indexOf方法

  • indexOf方法虽然简单，但是数组的indexOf兼容性较差，IE8及以下的浏览器是不支持的，不过可以将其转化为字符串再进行比较。
1
2
3
4
5
6
7
8
9
10
11
function single(origin) {
	var result = [];
	var item
	for(var i=0; i<origin.length; i++){
		item = origin[i]
		if(result.indexOf(item) === -1) {
			result.push(item)
		}
	}
	return result
}

三、数组的filter属性

  • filter接收的回调函数参数依次是：item(每一项) index(位置) array(数组自身)
  • filter函数接收一个回调函数，会创建自动创建一个新的数组来保存符合条件的项，并且会对数组中每一项进行判断，如果为true则返回给新创建的数组，如果为false则舍弃
  • 因为indexOf获取的是该item在数组中第一次出现的位置，所以如果这个indexOf得到的位置和自身的位置一样，则表示该值是唯一的。
  • 该方法的缺点是indexOf是ie9及以上的版本，filter是兼容到ie9，所以只有ie9可以用
1
2
3
4
5
6
7
8
function single(origin) {
	var result = origin.filter(function(item,index,array){
		// 如果indexOf检索出来的第一个位置，刚好与自身的位置相等的话，就返回
		// 否则就不会被添加到创建的新数组中，所以去重
		return array.indexOf(item) === index
	})
	return result
}

四、利用Object的key value

1)

  • 所有放入hashTable这个对象中的key为origin数组中的项，而且每一个key对应的value为true。所以先判断hashTable的值是否为true，如果为true，则表明此值在hashTable中已存在，不会进入if中执行；如果为false，则表明hashTable中没有这一项，则可以进入执行，将此值放入result中并且在hashTable中设置为true。
  • 此方法的时间复杂度是O(n)，但是对象的key默认是字符串类型，意味着1和”1”在key中是相等的。此方法不适合在含有字符串和数字混合的去重
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    function single(origin){
    var result = [];
    var hashTable = {};
    for (var i=0; i<origin.length; i++){
    	if(!hashTable[origin[i]]){
    		hashTable[origin[i]] = true
    		result.push(origin[i])
    	}
    }
    return result
    }

2）

  • 方法1的改良版，将key变为数组的项和数据类型拼接的字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
function single(origin){
	var result = [];
	var hashTable = {};
	for(var i=0; i<origin.length; i++){
		var current = origin[i]
		var key = typeof(current) + current
		if(!hashTable[key]){
			hashTable[key] = true
			result.push(current)
		}
	}
	return result
}

五、数组的sort方法

  • sort方法的优点在于利用了排序，返回后一个和前一个不相等的元素。比较简洁和直观，缺点在于改变了元素本来的排序位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function single(origin){
	return origin.concat.sort().filter(function(item,index,array){
		return !index || item!==origin[index-1]
	})
}
function single(array){
	array.sort()
	array.sort(function(a,b){
		return a-b
	})
	for(let i=0; i<array.length; i++){
		if(array[i] === array[i]+1){
			array.splice(i,1)
			i--
		}
	}
	return array
}

六、ES6的Set

  • ES6提供了一个数组结构Set，其特点是类似于数组，其成员的值都是唯一的，没有重复的值。向Set加入值的时候，不会发生类型转变，所以5和’5’是两个不同的值。Set内部判断两个值是否相同，用”===”,但是Set内部认为NaN等于NaN，includes也认为NaN等于NaN

  • ES6提供的数组转化方法Array.from()，将类数组对象或者可遍历的对象转化为一个真正的数组

    1
    2
    3
    function single(origin){
    return Array.from(new Set(origin))
    }

  • 简单书写方式：两种去重方式：

    1
    2
    3
    4
    5
    6
    7
    // 一、
    [...new Set(array)] // 去重
    // 二、
    function dedupe(arr) {
        return Array.from(new Set(arr));
    }
    dedupe([1,1,2,3])

七、ES6 Map

  • Map:其特点可以翻阅《ES6中Map集合》文章
  • Map.has(key)是检测指定的key在Map集合中是否已经存在
  • Map.set(item,true) 是存储该key和value
    1
    2
    3
    4
    5
    function single(origin){
    const map = new Map()
    return origin.filter((item) => !map.has(item) && map.set(item,true))
    }
    `

注意事项

  • 一些常见的数据类型是 === 和 indexOf是无法检测的：
1
2
3
4
5
6
7
console.log({} === {}) // false，新开一个对象，是在新的地址上挖坑，不同地址，肯定不相等
console.log(NaN === NaN) // false，ES6的includes和set才会判断NaN相等
console.log(/a/ === /a/) // false
console.log('1' === new String('1')) // false，但是如果是==，则相等
var arr = [NaN]
console.log(arr.indexOf(NaN)) // -1
// 不过Set中是可以去重NaN的