Famous interview questions:

How to implement array deduplication? Suppose you have an array array = [1,5,2,3,4,2,3,1,3,4] you write a function unique that makes unique(array) have the value [1,5,2,3,4]\

As soon as I saw this topic, what came into my mind was to use map method to reweight \

?????Copy the code

Well, just the general idea, here it is:

  • Take two numbers
  • Let’s see if there are any
  • If you don’t, put it in a new array. If you do, go back and find it again

It’s like a bunch of devices, 5D2, Mac, card reader, SD card, USB drive, footers, reflectors, sliders… Go out to take a film, if do not bring repeat the device, do I have to see which repeat one by one (traverse comparison), and then put in the bag (into a new array) \

Set

Similar to an array, except that the values of the members are unique and not duplicated. The Set itself is a constructor used to generate the Set data structure.

const s = new Set()
[2, 3, 5, 4, 5, 2, 2].forEach( x => s.add(x))
for(let i of s) {
    console.log(i)
} // 2 3 5 4
Copy the code

Obviously the Set structure does not add duplicate values. But it can take an array as an argument to initialize.

const set = new Set([1, 2, 3, 4, 4])
[...set] // [1, 2, 3, 4]
Copy the code

Set determines equality using === congruence but NaN is internally equal (amazing!) Two of these objects are always unequal

let set = new Set()
set.add({})
set.size // 1
set.add({})
set.size // 2
Copy the code

Two empty objects are not exactly equal, so they are treated as two values

Properties and methods of a Set instance

Instance attributes of the Set structure:

  • Set.prototype.constructorThe: constructor is Set by default
  • Set.prototype.size: Returns the total number of members of the Set instance

Operation method and traversal method

  • Add (): Adds a value and returns the Set structure itself
  • Delete (): Deletes a value and returns a Boolean value indicating whether the deletion was successful
  • Has (): Returns a Boolean value indicating whether the argument is a member of Set
  • Clear (): Clears all members with no return value
S.a dd (1). The add (2). The add (2) / 2 is added two s.s considering Sheldon horowitz at / / 2 as (1) / / true Sheldon horowitz as (2) / / true Sheldon horowitz as (3) / / false s.d. elete Sheldon horowitz at (2) the as / / (2) Const properties = {'width': 1, 'height': 1} if (properties(someName)) {// do something} const properties = new set () property.add ('width') properties.add('height') if (properties.has(someName)) { // do something }Copy the code

The array. from method converts a Set structure to an Array

const itrems = new Set([1, 2, 3, 4, 5])
const array = Array.from(items)
Copy the code

This provides a way to remove duplicate elements from an array (getting closer!!).

function dedupe(array) {
    return Array.from(new Set(array))
}

dedupe([1, 2, 1, 3]) // [1, 2, 3]
Copy the code

Wait, this can solve the above interview question??

!!!!!!!!! See the array here to redo solution 1: use Set implementation

function unique(array){ return Array.from(new Set(array)) } unique([1, 5, 2, 3, 4, 2, 3, 1, 3, 4]) // [[1, 5, 2, 3, Var unique = (a) => [...new Set(a)]Copy the code

There are many, many more solutions here

Map

Map objects hold key-value pairs. Any value (object or raw value) can be a key or a value. The constructor Map can take an array as an argument. Javascript objects are essentially collections of key-value pairs (hash structures), but only strings can be used as keys. So there’s a lot of limitations

The map was born

const data = {}
const element = document.querySeletor('myDiv')
data[element] = 'metadata'
data['[object HTMLDivElement]'] // "metadata"
Copy the code

A DOM node is used as the key of the Object data, but since objects only accept strings as key names, element is automatically converted to a string. ES6 provides the Map data structure \

  • It’s like an object, tooA collection of key-value pairs, but the scope of “key” is not limited to strings. All types of values (including objects) can be used as keys.Value valueIn data structures that require key-value pairs, the equivalent of Object is more appropriate than string value
const m = new Map()
const 0 = {p: 'Hellow World'}

m.set(o, 'content')
m.get(0) // "content"

m.has(o) // true
m.delete(o) // true
m.has(o) // flase
Copy the code

The above example shows how to add members to a Map. As a constructor, a Map can also take an array as an argument. The members of this array are arrays representing key-value pairs.

Const map = new map ([['name', 'zhang SAN '],  ['title', 'Author']]) map. The size / / 2 map) from the (' name ') / / true map. Get (' name ') / / 'zhang' map. From the (' title ') / / true map. Get (' title ') / / AuthorCopy the code

The name and title Map constructors, which specify two keys above, take an array as arguments and actually perform the following algorithm.

Const items = [['name', 'zhang 3 '],  ['title', 'Author'] ] const map = new Map() items.forEach( ({key, value}) => map.set(key, value) )Copy the code

That is, any data structure that has an Iterator interface and each member is a two-element array can be used as a Map constructor, and both sets and maps can be used to generate new maps

const set = new Set([
    ['foo', 1],
    ['bar', 2]
])
const m1 = new Map(set)
m1.get('foo') // 1

const m2 = new Map([['baz', 3]])
const m3 = new Map(m2)
m3.get('baz') // 3
Copy the code

Using a Set object and a Map object as arguments to the Map constructor results in new objects being generated. If you assign the same key more than once, the next value overwrites the previous value. If it is an unknown key, undefined is returned. Note: Only references to the same object are treated as the same key by the Map structure. \

const map = new Map()

map.set(['a'], 555)
map.get(['a']) // undefined
Copy the code

Set (getmap) = getmap (getmap) = getmap (getmap) = getmap (getmap) = getmap (getmap

The difference between Map and Object

  • aObjectThe key can only be a string orSymbols, but oneMapThe key of can be any value.
  • MapKeys in are ordered (FIFO), while keys added to objects are not.
  • MapThe number of key-value pairs can be obtained from the size property, andObjectThe number of key-value pairs can only be calculated manually.
  • ObjectEach has its own prototype, and the key name on the prototype chain may conflict with the key name you set on the object yourself.

Instance properties and operation methods

  • Size: Returns the number of key-value pairs contained in the Map object
  • Set (key, val): Adds new elements to the Map
  • Get (key): Finds a specific value by key value and returns it
  • Has (key): checks whether the Map object has the corresponding key value. Returns true if the Map object has the corresponding key value, and false otherwise
  • Delete (key): deletes data from the Map by key value
  • Clear (): Removes all elements from the Map

Traversal methods

  • keys(): returns a traverser for key names
  • values(): returns a traverser for key values
  • entries(): returns a traverser for key-value pairs
  • forEach(): Iterates through each member using the callback function

Array to heavy

Function unique(arr) {const res = new Map(); function unique(arr) {const res = new Map(); Return arr. Filter ((a) =>! res.has(a) && res.set(a, 1)) }Copy the code

Array de-heavy -Map implementation

  • Main idea: create a nullMap, iterating over the original array, taking each element of the array askeySave it in Map becauseMapWill not appear the same inkeySo I’m going to end up with thetaMapAll of thekeyThe value is the result of the decrement.
function arrayNonRepeatfy(arr) { let hashMap = new Map(); let result = new Array(); For (let I = 0; i < arr.length; If (hashmap. has(arr[I])) {if(arr[I]); } else {// If the key is not present in the hashMap, add hashmap.set (arr[I], false); result.push(arr[i]); } } return result; } let arr = [1, 1, 1, 2, 3, 3, 4, 5, 5, "a", "b", "a"]; console.log(arrayNonRepeatfy(arr)); // [ 1, 2, 3, 4, 5, 'a', 'b' ] console.log(hashMap); 0:{1 => true} {key: 1, value: true} 1:{2 => false} {key: 2, value: false} 2:{3 => true} {key: 3, value: true} 3:{4 => false} {key: 4, value: false} 4:{5 => true} {key: 5, value: true} 5:{"a" => true} {key: "a", value: true} 6:{"b" => false} {key: "b", value: false}Copy the code

The resulting Map not only de-duplicates the array, but also notes the repeatability of each element, making it easy to find duplicate numbers in the array:

Find the duplicate number in the array

At the end of the section, since every element in the hashMap is repeated, it is easy to find the number of repetitions, and iterate over the resulting hashMap, where the key is the number of repetitions:

function findRepeatNumInArray(arr) { let hashMap = new Map(); let result = new Array(); for (let i = 0; i < arr.length; Set (arr[I], hashmap. has(arr[I]))} For (let [key, value] of hashmap.entries ()) {if(value === true) {result.push(key); } } return result } let arr = [1, 1, 1, 2, 3, 3, 4, 5, 5, "a", "b", "a"]; console.log(findRepeatNumInArray(arr));Copy the code

Find the first non-repeating number in the array

[1, 1, 2, 2, 3, 4, 4, 5] 3 The code is similar to that in the previous section, iterating through the resulting hashMap, where the first value is false and the corresponding key is the first non-repeating number:

function findFirstNonRepeat(arr) { let hashMap = new Map(); for (let i = 0; i < arr.length; I ++) {hashmap.set (arr[I], hashmap.has (arr[I]))} For (let [key, value] of hashmap.entries ()) {if(value === false) {return key; }} return "all "; } let arr = [1, 1, 1, 2, 3, 3, 4, 5, 5, "a", "b", "a"]; console.log(findFirstNonRepeat(arr));Copy the code

To sum up, the core of the three problems is actually: using Map to store the repetition of each number. \

disadvantages

The disadvantage of set and map de-duplication is that objects do not de-duplication NaN, and compatibility is not good

Reference links

  • Ruan Yifeng’s INTRODUCTION to ES6 Standards (3rd Edition)
  • www.cnblogs.com/leftJS/p/11…
  • zhuanlan.zhihu.com/p/192673052