Examples of methods for deduplicating and flattening arrays in Javascript

Judgment of Arrays

Before talking about how to deduplicate and flatten arrays, let’s first talk about how to judge arrays, because in order to process arrays, of course, you must first judge whether the data passed is an array. .

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

The first method is to use instanceof

Instanceof is a method provided by ES5, which can be used to determine whether an instance is an instance of a certain class, for example:

[] instenceof Array
//返回结果是true

The disadvantage of this method is that it has poor compatibility. Some lower version browsers that do not support ES5 will be confused.

The second method is to judge through the prototype chain

If you understand js, you should understand that the characteristic of the js language is the prototype chain, and all objects inherit from Object.prototype , and there is a toString() method on the prototype. What is this toString() method used for? It returns the value of the current object in the form of a string. You may not understand this sentence when you read it for the first time. Here is an example:

var num = 123;
num.toString(); //返回结果为"123"

Do you understand it a little bit? It returns the string form of the object value num, which is "123". Okay, what does this have to do with judging arrays? Think about it, all objects inherit from Object.prototype, and so do arrays. If you send an array to Object.prototype as a "value" and call the toString() method, it should display the name of the object. Ah, this is the principle of judgment. The code is as follows:

Object.prototype.toString.call([]); //结果是"[object Array]"

This is the method used by isArray() of script libraries like jQuery.

Array Patting

After talking about it, let’s go straight to the topic. First, array Patting. What is Array Patting? Just pave [1,[2,[3,4],5]] into [1,2,3,4,5]. I have two ideas about array flattening. The second one is rather weird, so I’ll leave you with some suspense, haha.

The first is the conventional idea

Traverse the array. If there is an array inside the array, continue to traverse it until every element is traversed, and then stuff it in while traversing. In the new array variable, the flattening is completed. 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 and used. more convenient. One problem with this method is memory usage, because recursion will occupy a lot of memory if the amount of data is large.

The second weird idea

The second idea is to flatten the array without looking at it or traversing it. It sounds a little strange, how can you shoot flat without traversing? Just use the join() method to convert the array into a string, then remove the regular symbols and finally merge. When using this method, be careful not to join(""), because if divided like this, is 13 1 and 3 or 13? It’s hard to distinguish, 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 will convert the data type into a string.

Array deduplication

The following is array deduplication. 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 duplicates. The key is to be able to quickly determine whether elements are repeated.

There are still two ideas

The first traversal idea

is to prepare a new array variable, and traverse this variable each time to see if there is any If there are no duplicates, insert them. The new array generated is the array after deduplication. 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 method using hash judgment

The time complexity of the above method is O(n^2) It is not a good method. Its bottleneck is to determine whether it is repeated, so we switch to a more efficient method of retrieving whether it is repeated. This method is hashing. Why is hash retrieval the fastest? Let’s look through the data structure, I won’t go into details here.

The idea of ​​this method is to add a hash filter between the original array and the deduplicated array. Generally speaking, the original array data is handed over to the hash to see if there are duplicates. If not, add them. The specific code is as follows:

function uniqueArr(arr){
 var newArr = [],
 hashFilter = {};
 for(var i = 0;i<arr.length;i++){
 if(!hashFilter[arr[i]]){
 //若不存在将此属性对应的值改为true,并塞入去重数组中
 hashFilter[arr[i]] = true;
 newArr.push(arr[i]);
 }
 }
 return newArr;
}

I prefer the second type, because it is really fast to judge whether to repeat it, it can be said to be done in seconds.

Summary

The above is the entire content of this article. I hope the content of this article can bring some help to everyone's study or work. If you have any questions, you can leave a message to communicate.

For more examples of methods of deduplicating and flattening arrays in Javascript, please pay attention to the PHP Chinese website!