This is the 23rd day of my participation in Gwen Challenge

The premise

Interviewers often ask candidates a question when assessing their array base:

How to deduplicate an array?

This is a high frequency question, because it can test the interviewer’s familiarity with array methods, as well as thinking ability and algorithm ability. Let’s take a look today and see how many we can list.

Array to heavy

Question: How to deduplicate an array?

Examples: [1, 2, 3, 3, 3, 2, 5, 5, 6, 4, 1]

Expectations: [1, 2, 3, 5, 6, 4]

Here the elements of the array are primarily for primitive types, not reference types.

Double traversal

The first implementation:

let arr = [1.2.3.3.3.2.5.5.6.4.1]
for (let i = 0; i < arr.length; i++) {
  for (let j = i + 1; j < arr.length; j++) {
    if (arr[i] === arr[j]) {
      arr.splice(j, 1)
      // Because splice moves forward, j is subtracted by one
      j--
    }
  }
}
console.log(arr) // [1, 2, 3, 5, 6, 4] 
Copy the code

Principle:

The first iteration of the array, in this iteration, iterates over the array starting with I +1 (because repetition can only occur after I); If arr[I] === arr[j] is found in the second iteration, remove the element from j (or from I, not recommended, because the order changes). Note that after arr is removed,j is also subtracted by one (because arr is removed, the following element is moved forward).

The second implementation:

let arr = [1.2.3.3.3.2.5.5.6.4.1]
let isDuplicate = false
let uniqueArr = []
for (let i = 0; i < arr.length; i++) {
  isDuplicate = false
  for (let j = 0; j < uniqueArr.length; j++) {
    if (arr[i] === uniqueArr[j]) {
      isDuplicate = true}}// If there is no repetition, push the element to uniqueArr! isDuplicate && uniqueArr.push(arr[i]) }console.log(uniqueArr) // [1, 2, 3, 5, 6, 4] 
Copy the code

Principle:

Set a flag bit isDuplicate to compare the source array with the elements in the duplicate array. If any of the elements are equal, the duplicate is proved. Set the flag bit to true and do nothing. If not, the flag bit is false and the element is pushed into the deduplicated array.

IndexOf function

let arr = [1.2.3.3.3.2.5.5.6.4.1]
let uniqueArr = []
for (let i = 0; i < arr.length; i++) {
  if (arr.indexOf(arr[i]) === i) {
    uniqueArr.push(arr[i])
  }
}
console.log(uniqueArr) // [1, 2, 3, 5, 6, 4] 
Copy the code

Principle:

IndexOf (indexOf) (I) (uniqueArr) (uniqueArr) (uniqueArr) (I) (uniqueArr) (uniqueArr) (I) (uniqueArr) (uniqueArr) (uniqueArr) (uniqueArr)

The include function

let arr = [1.2.3.3.3.2.5.5.6.4.1]
let uniqueArr = []
for (let i = 0; i < arr.length; i++) {
  if(! uniqueArr.includes(arr[i])) { uniqueArr.push(arr[i]) } }console.log(uniqueArr) // [1, 2, 3, 5, 6, 4] 
Copy the code

Principle:

The include function returns a Boolean value that indicates whether the array already exists. If it does not exist, push the array to uniqueArr. If it does exist, push the array to uniqueArr.

The Set function

let arr = [1.2.3.3.3.2.5.5.6.4.1]
let uniqueArr= [...new Set(arr)]
console.log(uniqueArr) // [1, 2, 3, 5, 6, 4] 
Copy the code

Principle:

We take advantage of es6’s Set function, which has unique internal elements and no duplicate values, and finally turn it into an array with the spread operator.

The Map function

let arr = [1.2.3.3.3.2.5.5.6.4.1]
let uniqueArr = []
let map = new Map(a)for (let i = 0; i < arr.length; i++) {
  if(! map.get(arr[i])) { map.set(arr[i],true)
    uniqueArr.push(arr[i])
  }
}
console.log(uniqueArr) // [1, 2, 3, 5, 6, 4]
Copy the code

Principle:

If a Map element exists, return true. UniqueArr (uniqueArr) already exists.

The object’s hasOwnProperty

let arr = [1.2.3.3.3.2.5.5.6.4.1]
let uniqueArr = []
let obj = {}
for (let i = 0; i < arr.length; i++) {
  if(! obj.hasOwnProperty(typeof arr[i] + arr[i])) {
    obj[typeof arr[i] + arr[i]] = true
    uniqueArr.push(arr[i])
  }
}
console.log(uniqueArr) // [1, 2, 3, 5, 6, 4]
Copy the code

Principle:

This is done using the object’s hasOwnProperty function. HasOwnProperty (key) returns true if the object has a key that needs to be checked, and false otherwise. If hasOwnProperty returns true, it proves that uniqueArr already exists and does not need to be pushed.

Typeof arr[I] + arr[I]; typeof arr[I] + arr[I]; typeof arr[I];

The sort order

let arr = [1.2.3.3.3.2.5.5.6.4.1]
let uniqueArr = []
arr.sort() 
for (let i = 0; i < arr.length; i++) {
  if(arr[i] ! == arr[i +1]) {
    uniqueArr.push(arr[i])
  }
}
console.log(uniqueArr) // [1, 2, 3, 4, 5, 6]
Copy the code

Principle:

A sort function is used to sort and iterate through the array. If the adjacent elements are not equal, prove that uniqueArr does not already have the element and then push it into the array. Otherwise, it is not processed.

The reduce function

let arr = [1.2.3.3.3.2.5.5.6.4.1]
let uniqueArr = arr.sort().reduce((acc, cur, i) = > {
  if (acc.length === 0 || acc[acc.length - 1] !== cur) {
    acc.push(cur)
  }
  return acc
}, [])

console.log(uniqueArr) // [1, 2, 3, 4, 5, 6]
Copy the code

Principle:

Mainly use reduce function, sort first, then pass in a new array, and judge if the length of the new array is equal to 0 or the elements of the new array are compared with traversal elements, if not, push elements.

conclusion

The overall idea is mainly as follows:

  • Go through the set of numbers twice, eliminate the ones that are equal, and then go through
  • Create a new empty array, iterate over the array, if the empty array does not have the element, thenpushInto an empty array
  • Using objects /MapKey does not repeat
  • usingSetThe uniqueness of the elements of
  • Sort the array, then iterate through the array, comparing left and right, if not equalpushInto an empty array

Recommendation:

Object /Map, Set scheme is better, the complexity is not high, NaN can be de-heavy, other scheme complexity is higher.

The above is my summary of the array to duplicate N methods, you can start knocking try, understand the principle is not afraid of the interviewer asked ~