Array sorting and deduplicating, has been a hot topic in the interview, generally requires handwritten array deduplicating method code, because it can be a good test of a person’s logical thinking ability. If you are asked, what are the methods of array de-duplication? If you can answer 10 of these questions, there’s a good chance you’ll impress your interviewer. These knowledge as long as through a certain amount of deliberate training, look more, think more, more code, these algorithms to master is actually a very simple thing.
The full text is divided into two parts, array sorting and array deduplicating.
Array deduplication
Create an empty array and use indexOf to deduplicate it
function unique(arr) {
if(! Array.isArray(arr)) { console.log('type error! ')
return} var array = []; // Define an empty arrayfor (var i = 0; i < arr.length; i++) {
if(array.indexof (arr[I]) === -1) {array.push (arr[I])}}returnarray; } var arr = [1,1, 1]'true'.'true'.true.true, 15, 15,false.false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a'.'a', {}, {}]; console.log(unique(arr)) // [1,"true".true, 15, false, undefined, null, NaN, NaN, "NaN", 0, "a", {... }, {... }] //NaN, {} are not deduplicatedCopy the codeCreate an empty result array, loop through the original array, check whether the result array has the current element, skip if they have the same value, push into the array if they do not.
2. Use “for” to nest “for” and then splice to unduplicate it (most commonly used in ES5)
Method one:
Double loop, outer loop elements, inner loop when comparing values. If the values are the same, delete this value.
function unique(arr){
for(var i=0; i<arr.length; i++){
for(var j=i+1; j<arr.length; j++){
if(arr[I]==arr[j]){// if arr[I]==arr[j]); j--; }}}returnarr; } var arr = [1,1, 1]'true'.'true'.true.true, 15, 15,false.false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a'.'a', {}, {}]; console.log(unique(arr)) //[1,"true", 15, false, undefined, NaN, NaN, "NaN"."a", {... }, {... }] //NaN and {} are not reweightedCopy the codeMethod 2:
Var arr =,22,33,44,55,22,33,54 [11];for(var n=0; n<arr.length; n++){if(arr.indexOf(arr[n])! Arr. LastIndexOf (arr[n]); arr. LastIndexOf (arr[n]); arr. n--; }} console.log(arr);}} console.log(arr);Copy the code3, use ES6 Set to remove weights (most commonly used in ES6)
function unique (arr) {
returnArray.from(new Set(arr))} var arr = [1,1,'true'.'true'.true.true, 15, 15,false.false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a'.'a', {}, {}]; console.log(unique(arr)) //[1,"true".true, 15, false, undefined, null, NaN, "NaN", 0, "a", {}, {}]Copy the codeRegardless of compatibility, this method of de-duplication has the least code. This method also does not remove the empty ‘{}’ object; later higher-order methods add methods to remove the duplicate ‘{}’ object.
4, use sort()
function unique(arr) {
if(! Array.isArray(arr)) { console.log('type error! ')
return;
}
arr = arr.sort()
var arrry= [arr[0]];
for (var i = 1; i < arr.length; i++) {
if (arr[i] !== arr[i-1]) {
arrry.push(arr[i]);
}
}
returnarrry; } var arr = [1,1, 1]'true'.'true'.true.true, 15, 15,false.false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a'.'a', {}, {}]; console.log(unique(arr)) // [0, 1, 15,"NaN"NaN, NaN, {... }, {... },"a".false, null, true."true"}, undefined] //NaN, {Copy the codeUse sort() sorting method, and then traverse and compare adjacent elements according to the sorted result.
5, the use of object attributes can not be the same characteristics of the deduplication (this array deduplication method has problems, not recommended, need to improve)
function unique(arr) {
if(! Array.isArray(arr)) { console.log('type error! ')
return
}
var arrry= [];
var obj = {};
for (var i = 0; i < arr.length; i++) {
if(! obj[arr[i]]) { arrry.push(arr[i]) obj[arr[i]] = 1 }else {
obj[arr[i]]++
}
}
returnarrry; } var arr = [1,1, 1]'true'.'true'.true.true, 15, 15,false.false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a'.'a', {}, {}]; console.log(unique(arr)) //[1,"true", 15, false, undefined, null, NaN, 0, "a", {... / / two}]trueJust get rid of NaN and {}Copy the code6. Use includes
function unique(arr) {
if(! Array.isArray(arr)) { console.log('type error! ')
return
}
var array =[];
for(var i = 0; i < arr.length; i++) {
if(! Array.push (arr[I]); array.push(arr[I]); }}returnArray} var arr = [1,1,'true'.'true'.true.true, 15, 15,false.false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a'.'a', {}, {}]; console.log(unique(arr)) //[1,"true".true, 15, false, undefined, null, NaN, "NaN", 0, "a", {... }, {... }] //{} is not deduplicatedCopy the codeUse hasOwnProperty
function unique(arr) {
var obj = {};
return arr.filter(function(item, index, arr){
return obj.hasOwnProperty(typeof item + item) ? false : (obj[typeof item + item] = true)})} var arr = [1, 1,'true'.'true'.true.true, 15, 15,false.false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a'.'a', {}, {}]; console.log(unique(arr)) //[1,"true".true, 15, false, undefined, null, NaN, "NaN", 0, "a", {... }] // All of them are unloadedCopy the codeUse hasOwnProperty to determine whether an object property exists
8. Use filter
function unique(arr) {
return arr.filter(function(item, index, arr) {// The current element, the first index in the original array == the current index value, otherwise return the current elementreturnarr.indexOf(item, 0) === index; }); } var arr = [1,1, 1]'true'.'true'.true.true, 15, 15,false.false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a'.'a', {}, {}]; console.log(unique(arr)) //[1,"true".true, 15, false, undefined, null, "NaN", 0, "a", {... }, {... }]Copy the code9. Use recursion to duplicate
function unique(arr) {
var array= arr;
var len = array.length;
array.sort(function(a,b){// It is more convenient to remove the weight after sortingreturn a - b;
})
function loop(index){
if(index >= 1){
if(array[index] === array[index-1]){ array.splice(index,1); } loop(index - 1); }} loop(len-1);returnarray; } var arr = [1,1, 1]'true'.'true'.true.true, 15, 15,false.false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a'.'a', {}, {}]; console.log(unique(arr)) //[1,"a"."true".true, 15, false, 1, {... }, null, NaN, NaN,"NaN", 0, "a", {... }, undefined]Copy the code10. Use Map data structure to remove weight
function arrayNonRepeatfy(arr) {
let map = new Map();
letarray = new Array(); // The array is used to return the resultfor (let i = 0; i < arr.length; i++) {
ifMap.has (arr[I])) {// If map.set (arr[I],true);
} else {
map .set(arr[i], false); Array.push (arr[I]); }}returnarray ; } var arr = [1,1, 1]'true'.'true'.true.true, 15, 15,false.false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a'.'a', {}, {}]; console.log(unique(arr)) //[1,"a"."true".true, 15, false, 1, {... }, null, NaN, NaN,"NaN", 0, "a", {... }, undefined]Copy the codeCreate an empty Map data structure that iterates through the array to be repealed, storing each element of the array as a key in the Map. Since the Map does not have the same key value, the final result is the result after the deduplication.
11. Use reduce+includes
function unique(arr){
returnarr.reduce((prev,cur) => prev.includes(cur) ? prev : [...prev,cur],[]); } var arr = [1,1, 1]'true'.'true'.true.true, 15, 15,false.false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a'.'a', {}, {}]; console.log(unique(arr)); / / [1,"true".true, 15, false, undefined, null, NaN, "NaN", 0, "a", {... }, {... }]Copy the code12, new Set (arr)] […
[...new Set(arr)] ----Copy the codeTwo. Multidimensional array flattening
A multidimensional array is converted into a one-dimensional array, and then it is de-duplicated, ascending,
Method 1:
function f (arr) {
if(Object.prototype.toString.call(arr) ! ='[object Array]') {// Check whether it is an arrayreturn;
}
var newarr = [];
function fn (arr) {
for (var i = 0; i < arr.length; i++) {
if (arr[i].length) {
fn(arr[i]);
}else{
newarr.push(arr[i]);
}
}
}
fn(arr);
return newarr;
}
Array.prototype.u = functionVar newarr = []; var obj = {};for (var i = 0; i < this.length; i++) {
if (!obj[this[i]]) {
newarr.push(this[i]);
obj[this[i]] = 1;
}
}
return newarr;
}
functionCompare (c1,c2) {// compare (c1,c2)return c1 -c2;
}
var arr = [2, -5, 6, [6, -5, [2, 5], [8, 10, [6, 8], -3], 2], 5]
var a = [];
a = f(arr);
b = a.u();
c = b.sort(compare);
console.log(c);Copy the codeMethod 2:
Array.prototype.flat= function() {
return[].concat(... this.map(item => (Array.isArray(item) ? item.flat() : [item]))); } Array.prototype.unique =function() {
return [...new Set(this)]
}
const sort = (a, b) => a - b;
console.log(arr.flat().unique().sort(sort));Copy the codeMethod 3:
function spreadArr(arr=[]){
if(arr.some(ele=>Array.isArray(ele))){
let newArr = [];
arr.forEach((ele) => {
if(Array.isArray(ele)){ newArr = newArr.concat(... ele) }else{
if(! newArr.includes(ele)) newArr.push(ele) } })return spreadArr(newArr);
}
return arr.sort((a,b)=> a-b);
}
spreadArr([ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10]);Copy the codeMethod 4:
var arr = [2, -5, 6, [6, -5, [2, 5], [8, 10, [6, 8], -3], 2], 5];
function f (arr) {
var newarr = [];
function fn (arr) {
for (var i = 0; i < arr.length; i++) {
if (arr[i].length) {
if(array.isarray (arr[I])) {array.isarray (arr[I]) {array.isarray (arr[I]); }else {
newarr.push(arr[i]);
}else{
newarr.push(arr[i]);
}
}
}
fn(arr);
return newarr;
}
var x = f(arr);
var newarr = [];
for(var n = 0; n < x.length; n++) {if (newarr.indexOf(x[n]) == -1) {
newarr.push(x[n]);
}
}
newarr.sort((a, b) => a - b)
console.log(newarr)Copy the codeMethod 5:
One of my friends in the comments section, and I think it’s also a good idea, multidimensional arrays into one-dimensional arrays,
var arr = [12, 23, 34, [6, [6], [6,[7,[8]]]], [5,[5]], [4, [7]], [4, [[3]]], 45, 6];
arr.toString().split(', ').map(Number); / / [12, 23, 34, 6, 6, 6, 7, 8, 5, 5, 4, 7, 4, 3, 45, 6]Copy the codeBut if there are Chinese characters (or other strings) inside, it can not be converted to pure numbers. It is recommended to use the algorithm class method described above.
Classic interview questions
1. Push and pop of the stack
Enter two sequences of integers. The first sequence represents the push order of the stack. Determine whether the second sequence is likely to be the eject order of the stack. Assume that all the numbers pushed are not equal. For example, sequence 1,2,3,4,5 is the pushdown sequence of a stack, and sequence 5,4,3,2,1 or 3,2,1 is an eject sequence corresponding to the pushdown sequence, but 4,3,5,1,2 cannot be the eject sequence of the pushdown sequence.
function IsPopOrder(pushV,popV){
if(pushV.length === 0) return false; var stack = []; / / simulation stackfor(var i = 0, j = 0; i < pushV.length;) { stack.push(pushV[i]); i += 1; // Pushed values need to be ejectedwhile(j < popV.length && stack[stack.length-1] === popV[j]){
stack.pop();
j++;
if(stack.length === 0) break; }}return stack.length === 0;
}Copy the code2. Use stacks to simulate queues
Ideas:
- On the stack
AAdd data. - If the stack
BEmpty, loop will stackAPopup the contents into the stackBAnd pop the stackBThe last item - If the stack
BIf it is not empty, it pops the stack directlyBThe last term
ar stackA = [];
var stackB = [];
function push(node){
stackA.push(node);
}
function pop() {if(! stackB.length){while(stackA.length){ stackB.push(stackA.pop()); }}return stackB.pop();
}Copy the code3. Find the longest consecutive string that does not repeat itself
In a string to find a continuous not repeated maximum length of the string, solve this kind of problem:
- Loop over the string until repetition occurs
- For each overlay, record the maximum length of the string
// The longest continuous string that does not repeat itselffunction getMaxLenStr(str) {
var cur = [];
var maxLenStr = ' ';
for(var i = 0; i < str.length; i++) {
if(! cur.includes(str[i])) { cur.push(str[i]); }else{ cur = []; // null cur.push(STR [I]); } // Stores the maximum length of a stringif(maxLenStr.length < cur.length) {
maxLenStr = cur.join(' '); }}return maxLenStr;
}
getMaxLenStr('ababcabcde'); // abcdeCopy the codeMethod 2:
var str = "aababcabcdeabcdefaababc";
var x = str.split(' ').reduce((a, b, index) => {
if(a.indexOf(b) ! = = 1) {return a;
}
a.push(b);
return a;
}, []).join(' ');
console.log(x) Copy the codeMethod 3:
var s = "aababcabcdeabcdefaababc";
var lengthOfLongestSubstring = function(s) {
var str = ""; // 用于存放无重复字符串
var arr = [];
for(var i = 0; i < s.length; i++) {
var char = s.charAt(i);
var index = str.indexOf(char);
if(index === -1) {
str += char;
arr.push(str);
} else{ str = str.substr(index + 1) + char; }}return arr.reduce((a, b) => {
return b.length > a.length ? b : a;
}, ' ');
};
console.log(lengthOfLongestSubstring(s));Copy the code4. Find the maximum sum of continuous subvectors in an array.
function FindGreatestSumOfSubArray(arr) {
let sum = arr[0];
let max = arr[0];
for(let i = 1; i < arr.length; i++) {
if(sum < 0) {
sum = arr[i];
}else{ sum += arr[i]; } // Record the maximum valueif(max < sum) { max = sum; }}return max;
} Copy the code5. Given an encoding character, decode it according to the encoding rules and output a character string
Encoding rule: coount[letter] : outputs the letter count times. Count is 0 or a positive integer. Letter is a case-sensitive pure letter. Example:
const s= 3[a]2[bc]; decodeString(s);/ / return'aaabcbc'const s= 3[a2[c]]; decodeString(s);/ / return'accaccacc'const s= 2[ab]3[cd]ef; decodeString(s);/ / return'ababcdcdcdef'
If the content of push is’] ‘, then loop the pop character until it meets’ [‘, then arrange the string of pop character according to the rule, push it into the stack again, and finally splice the contents in the stack into string output.
Method 1:
function decodeString(str) {
letstack = []; // Stack to store stringsfor (let i = 0; i < str.length; i++) {
let cur = str[i];
if(cur ! = ='] ') {
stack.push(cur);
} else{/ / pop uplet count = 0;
let loopStr = [];
let popStr = ' ';
while((popStr = stack.pop()) ! = ='[') { loopStr.unshift(popStr); } count = stack.pop(); // Add the resultlet item = ' ';
for (let i = 0; i < count; i++) {
item += loopStr.join(' '); } stack.push(... (item.split(' '))); }}return stack.join(' ');
}Copy the codeMethod 2:
const str = '3[a]2[bc]';
function decodeString(str) {
let Counts = str.split(/\[[a-zA-Z]+\]/);
let Letters = str.match(/[a-zA-Z]+/g);
let newString = "";
Letters.forEach((item,index)=>{
for(var n=0; n<Counts[index]; n++) { newString += item; }})return newString;
}
console.log(decodeString(str))Copy the code6. Implement a method that limits the number of occurrences of an element in an array. The first parameter is an array, and the second parameter is an array. The order of the element groups should not be changed;
Such as:
deleteNth((1, 1 1, 1), 2); //return [1, 1]
deleteNth((20, 37, 34, 20, 20, 37), 2); //return[20, 37, 34, 20, 37]Copy the codeMethod 1:
var arr = [4, 4, 4, 4, 3, 3, 3, 3, 1, 2, 4, 3, 90];
function deleteNth(arr, n) {
var newArr = [];
for (var i = 0; i < arr.length; i++) {
if(newArr.indexOf(arr[i]) == -1) { newArr.push(arr[i]); }}for (var i = 0; i < newArr.length; i++) {
var sum = 0;
for (var j = 0; j < arr.length; j++) {
if (arr[j] == newArr[i]) {
sum ++;
if(sum > n) { arr.splice(j, 1); j--; }}}}return arr;
}
console.log(deleteNth(arr, 2))Copy the codeMethod 2:
var arr = [1, 1, 2, 5, 23, 23, 1, 1];
function deleteNth(arr, n) {
let newArr = arr.map( item => {
returnitem; })// Original data copyletnewArr1 = []; // Processed datafor (var i = 0; i < newArr.length; i++) {
if (newArr1.indexOf(newArr[i]) < 0) {
newArr1.push(newArr[i]);
} else if (newArr1.indexOf(newArr[i]) > -1) {
lethasIndexArr = []; // The index used to store the matching itemsfor (let j = 0; j < newArr1.length; j++) {
if(newArr1[j] == newArr[I]) {// Throw the index of the matched item into hasIndexArr hasIndexArr.push(j); }}if(hasIndexArr.length < n) {// If the number does not meet n, throw in newarr1.push (newArr[I]); }// If the number is satisfied, skip}}return newArr1;
}
console.log(deleteNth(arr,1))Copy the codeMethod 3:
var arr = [4, 4, 4, 4, 3, 3, 3, 3, 1, 2, 4, 3, 90];
var cache = {};
function deleteNth(arr, x) {
return arr.filter(function (n) {
cache[n] = (cache[n]||0) + 1;
return cache[n] <= x;
})
}
console.log(deleteNth(arr, 1))Copy the code6. Implement a method that looks for a value in an array as a cut-off point so that the numbers on the left and right sides of the value add up to the same value
[1, 2, 3, 4, 3, 2, 1] = > returns the subscript 3 [1, 100, 50, 51 -, 1, 1] = > returns the subscript 1Copy the codeMethod 1:
var arr = [1, 2, 3, 4, 3, 2, 1];
function find (arr) {
var sum1 = 0;
for (var i = 0 ; i < arr.length ; i ++) {
sum1 += arr[i];
var sum2 = 0;
for (var j = i + 2 ; j < arr.length ; j ++) {
sum2 += arr[j];
}
if (sum1 == sum2) {
return i + 1;
} else if(i == arr.length - 3 && sum1 ! == sum2) {return "This value does not exist";
}
}
}
console.log(find(arr))Copy the codeMethod 2:
var arr = [1, 2, 3, 4, 3, 2, 1];
for (var i = 0 ; i < arr.length - 2 ; i ++) {
var arr1 = arr.slice(0, i+1);
var arr2 = arr.slice(i+2);
var sum1 = sum2 = 0;
for (var m = 0 ; m < arr1.length ; m ++) {
sum1 += arr1[m];
}
for (var n = 0 ; n < arr2.length ; n ++) {
sum2 += arr2[n];
}
if (sum1 == sum2) {
console.log(i + 1);
break;
} else if(i == arr.length - 3 && sum1 ! == sum2) { console.log("This value does not exist"); }}Copy the code7. Customize events
var content = document.querySelector('.content'); Var evt = new Event('custom');
var customEvt = new CustomEvent('customEvt', {// Pass the parameter detail: {name:'tom',
age: 12
}
});
content.addEventListener('custom', (e) => {
console.log('Custom event is triggered with no arguments... ');
console.log(e);
});
content.addEventListener('customEvt', (e) => {
console.log('Custom event is triggered with arguments... '); console.log(e); console.log(e.detail); }); // Trigger this custom event when clicked'click', (e) => {
content.dispatchEvent(evt);
content.dispatchEvent(customEvt);
});Copy the code4. Array sort
A. sort B. sort C. sort D. sort
(1) Simple sort of simple array
Var arrSimple = new Array (1,8,7,6); arrSimple.sort(); console.log(arrSimple.join()) ;Copy the code(2) Custom sort of simple array
Var arrSimple2 = new Array (1,8,7,6); arrSimple2.sort(function(a,b){
return a-b
});
console.log(arrSimple2.join())Copy the code
Explanation: A,b represent any two elements in the array, a-b output sorted from smallest to largest, b-A output sorted from largest to smallest.
(3) Simple object List custom attribute sorting
var objectList = new Array();
function Persion(name,age){
this.name=name;
this.age=age;
}
objectList.push(new Persion('jack', 20)); objectList.push(new Persion('tony', 25)); objectList.push(new Persion('stone', 26)); objectList.push(new Persion('mandy', 23)); // Sort objectList.sort(function(a,b){
return a.age-b.age
});
for(var i=0; i<objectList.length; i++){ document.writeln('<br />age:'+objectList[i].age+' name:'+objectList[i].name);
}Copy the code
(4) Sorting of editable attributes by simple object List
var objectList2 = new Array();
function WorkMate(name,age){
this.name=name;
var _age=age;
this.age=function() {if(! arguments){ _age=arguments[0]; }else{
return _age;
}
}
}
objectList2.push(new WorkMate('jack', 20)); objectList2.push(new WorkMate('tony', 25)); objectList2.push(new WorkMate('stone', 26)); objectList2.push(new WorkMate('mandy', 23)); Sort by age objectList2.sort(function(a,b){
return a.age()-b.age();
});
for(var i=0; i<objectList2.length; i++){ document.writeln('<br />age:'+objectList2[i].age()+' name:'+objectList2[i].name);
}Copy the codeSee my article for more on sorting
Top 10 Classic sorting algorithms (Python and JavaScript)