How to implement array deduplication?

Array = [1,5,2,3,4,2,3,1,3,4]

You’re going to write a function unique that makes

Unique (array) has the value [1,5,2,3,4]

That is, you get rid of all the duplicate values and keep only the non-duplicate values.

Method 1: Use indexOf

function uniqueByIndexOf(array) {
    var tempArray = [];
    for (let i = 0; i < array.length; i++) {
        if (tempArray.indexOf(array[i]) === -1) { tempArray.push(array[i]); }}return tempArray;
}
Copy the code

Algorithm analysis

IndexOf itself is a single layer circular operation, so the algorithm of uniqueByIndexOf function is actually a double layer circular operation. Therefore, the time complexity of the algorithm is O(n²), and the running speed is not fast. In terms of space, the algorithm introduces the array object tempArray to open up new memory space.

Method 2: Use Set

function uniqueBySet(array) {
    const s = new Set(a); array.forEach(item= > s.add(item));
    return Array.from(s);
}
Copy the code

Algorithm analysis:

A Set is a new data structure provided by ES6. It is similar to an array, but the values of its members are unique and there are no duplicate values.

Because Set is an array-based data structure, the algorithm of uniqueBySet function and uniqueByIndexOf are double loops. The time complexity of the algorithm is O(n²) and the running speed is not fast. In space, the algorithm introduces the Set object S to open up a new memory space.

Method 3: Use Map

function uniqueByMap(array) {
    const m = new Map(a);for (let i = 0; i < array.length; i++) {
        if(! m.has(array[i])) { m.set(array[i],0); }}return [...m.keys()];
}
Copy the code

Algorithm analysis:

Map is also a new data structure provided by ES6. It is a collection of key-value pairs similar to objects, but the range of “keys” is not limited to strings. Values of all types (including objects) can be used as keys. In other words, the Object structure provides string-value mapping, and the Map structure provides value-value mapping, which is a more complete Hash structure implementation. If you need key-value data structures, Map is better than Object.

Since Map is a hash based data structure, the time complexity of search (HAS) and insert (set) operations is O(1), so the time complexity of uniqueByMap algorithm is O(n), which is the most efficient algorithm among the three algorithms in this paper.

In terms of space, the algorithm introduces the Map object M to open up new memory space. Maps take up more memory than arrays and sets when the program is running, which can be considered a minor drawback of the uniqueByMap algorithm.