Example of Array Deduplication and Flat Method in Javascript

Judgment of array

Before talking about how to deduplicate and flatten the array, first talk about how to judge the array, because to deal with the array, of course, it is necessary to judge whether the data passed down is an array.

First of all, we all know that there are only five data types of js, which are Undefined, Null, Boolean, Number and String. The array is only one object. Use typeof([]) The returned result is a string of Object, so we need to judge it by other means, so we will say two methods here.

The first method uses instenceof method

instanceof is a method provided by ES5, which can be used to determine whether an instance is an instance of a class, such as:

[] instenceof Array
// The result returned is true

The disadvantage of this method is that its compatibility is not good, and those who do not support ES5 in a lower version of browsers will be overwhelmed.

The second method is to judge by prototype chain

If you know js, you should know that js is characterized by prototype chain, and all objects inherit from Object.prototype And on prototype toString() Method, this toString() What is the method for? Is to return the value of the current object as a string. The first time I look at this sentence, I may not understand it. For example:

var num = 123;
num.toString(); // The result returned is "123"

Did you see point 1 clearly? Is to return the value of num as a string, that is, "123". OK, what does this have to do with judging arrays? Think that all objects inherit from Object.prototype So is the array. If you send an array to Object.prototype As a "value" in the call toString() Method, then it should show the name of this object. This is the principle of judgment. The code is as follows:

Object.prototype.toString.call([]); // The result is "[object Array]"

Of a script library like jQuery isArray() This is the method used.

Array flattening

After that, let's get to the point. First, the array is flat. What is array flat? Is to lay [1, [2, [3, 4], 5] into [1, 2, 3, 4, 5]. I have two ideas about array shooting. The second one is wonderful. Leave some suspense.

The first is the conventional thinking

Traversing the array, if the array is set inside the array, continue to traverse inside, until each element is traversed, and then 1 edge traversal 1 edge into the new array variables, so that the completion of the flat, the specific code is as follows:

panelArr = function(arr){
 var newArr = [];
 var isArray = function(obj) {
  return Object.prototype.toString.call(obj) === '[object Array]';
 };
 var dealArr = function(arr){
  for (var i = 0;i<arr.length;i++){
   isArray(arr[i]) ? dealArr(arr[i]) : newArr.push(arr[i]);
  }
 };
 dealArr(arr);
 return newArr;
};
console.log(panelArr([1,[2,3]])); //[1,2,3]

Of course, this method can also be written in Array.prototype It is more convenient to use. One problem with this method is the memory footprint, because recursion will take up a lot of memory if the amount of data is large.

The second wonderful idea

The second way of thinking is not to look at the array, nor to traverse it directly. It sounds a little strange. How can you shoot flat without traversing? Is to use join() Method, convert the array into a string, then regularly remove symbols and finally merge. Note that this method cannot be used Object.prototype0 Because if you divide it like this, is 13 1 and 3 or 13? It is difficult to distinguish, and the code is as follows:

var arr = [1,2,[33,43],20,19];
arr.join(".").replace(/,/g,".").split("."); //["1", "2", "33", "43", "20", "19"]

Note: This method converts the data type to a string.

Array de-duplication

The following is the array de-duplication, for example, [1, 2, 3, 3, 4, 5, 5, 5, 6] becomes [1, 2, 3, 4, 5, 6]. The core of this implementation is to remove duplication here, and it is the key to quickly judge whether elements are duplicated or not.

Or two ways of thinking

The first idea of traversal

That is, prepare a new array variable, traverse this variable every time before inserting it to see if there are duplicates, if not, insert it, and finally generate a new array that is the array after de-duplication. The sample code is as follows:

function uniqueArr(arr){
 var newArr = [];
 newArr.push(arr[0]);
 for(var i = 1; i<arr.length;i++){
 var repeat = false;
 for(var j = 0;j<newArr.length;j++){
 if(arr[i] == newArr[j]){
 repeat = true;
 }
 }
 if(!repeat){
 newArr.push(arr[i]);
 }
 }
 return newArr;
}

The second uses hash judgment

The time complexity above is O(n^2) The method is not a good method, its bottleneck is to judge whether it is repeated here, so we replace it with a more efficient method to retrieve whether it is repeated. This method is hash. Why is hash retrieval the fastest? Look through the data structure, so I won't go into details here.

The idea of this method is to add a hash filter between the original array and the deduplication array. Generally speaking, the original array data is handed over to the hash to see if there is duplication, and if not, it is added. The specific code is as follows:

function uniqueArr(arr){
 var newArr = [],
 hashFilter = {};
 for(var i = 0;i<arr.length;i++){
 if(!hashFilter[arr[i]]){
 // If it does not exist, change the value corresponding to this property to true, And stuffed into the de-duplication array 
 hashFilter[arr[i]] = true;
 newArr.push(arr[i]);
 }
 }
 return newArr;
}

I prefer the second kind, because it is really fast to judge whether to repeat here, so to speak, it is seconds out.

Summarize

The above is the whole content of this article. I hope the content of this article can bring 1 certain help to everyone's study or work. If you have any questions, you can leave a message for communication.