Najjednostavniji kod za prelazak niza u javascript

Što je najlakše, besplatno za knjižnicu kod za implementaciju presjeka polja u javascript? Želim pisati

 intersection([1,2,3], [2,3,4,5]) 

i dobiti

 [2, 3] 
356
11 дек. Peter je postavljen 11. prosinca. 2009-12-11 06:04 '09 u 6:04 AM 2009-12-11 06:04
@ 35 odgovora
  • 1
  • 2

Koristite kombinaciju Array.prototype.filter i Array.prototype.indexOf .

 array1.filter(function(n) { return array2.indexOf(n) !== -1; }); 
675
odgovor je dat . 11. prosinca 2009-12-11 06:08 '09 u 6:08 am 2009-12-11 06:08

Čini se da je destruktivno najjednostavnije, pogotovo ako možemo pretpostaviti da je unos sortiran:

  function intersection_destructive(a, b) { var result = []; while( a.length > 0  b.length > 0 ) { if (a[0] < b[0] ){ a.shift(); } else if (a[0] > b[0] ){ b.shift(); } else  { result.push(a.shift()); b.shift(); } } return result; } 
border=0

Proces bez razaranja mora biti složeniji jer moramo pratiti pokazatelje:

  function intersect_safe(a, b) { var ai=0, bi=0; var result = []; while( ai < a.length  bi < b.length ) { if (a[ai] < b[bi] ){ ai++; } else if (a[ai] > b[bi] ){ bi++; } else  { result.push(a[ai]); ai++; bi++; } } return result; } 
149
11 дек. odgovor je dan atk 11 dec. 2009-12-11 06:45 '09 u 6:45 am 2009-12-11 06:45

Ako vaša okolina podržava skup ECMAScript 6 , jedan jednostavan i vjerojatno djelotvoran način (pogledajte vezu specifikacija):

 function intersect(a, b) { var setA = new Set(a); var setB = new Set(b); var intersection = new Set([...setA].filter(x => setB.has(x))); return Array.from(intersection); } 

Kraći, ali manje čitljiv (i bez stvaranja dodatnog Set ):

 function intersect(a, b) { return [...new Set(a)].filter(x => new Set(b).has(x)); } 

Imajte na umu da će implementacija skupa dopustiti samo jedinstvene vrijednosti, tako da se new Set[1,2,3,3].size procjenjuje na 3 .

28
05 мая '16 в 6:21 2016-05-05 06:21 odgovor je dao nbarbosa 05 svibanj '16 u 6:21 2016-05-05 06:21

Korištenje Underscore.js

 _.intersection( [0,345,324] , [1,0,324] ) // gives [0,324] 
17
29 сент. Odgovor je dao Sai Ram 29. rujna 2016-09-29 10:51 '16 u 10:51 2016-09-29 10:51

Korištenje jQuery :

 var a = [1,2,3]; var b = [2,3,4,5]; var c = $(b).not($(b).not(a)); alert(c); 
11
25 дек. odgovor je dao Gowsikan 25 dec. 2013-12-25 10:20 '13 u 10:20 2013-12-25 10:20

Kako je jednostavno koristiti asocijativne nizove?

 function intersect(a, b) { var d1 = {}; var d2 = {}; var results = []; for (var i = 0; i < a.length; i++) { d1[a[i]] = true; } for (var j = 0; j < b.length; j++) { d2[b[j]] = true; } for (var k in d1) { if (d2[k]) results.push(k); } return results; } 

promijeniti:

 // new version function intersect(a, b) { var d = {}; var results = []; for (var i = 0; i < b.length; i++) { d[b[i]] = true; } for (var j = 0; j < a.length; j++) { if (d[a[j]]) results.push(a[j]); } return results; } 
10
11 дек. Odgovor daje Steven Huwig 11. prosinca. 2009-12-11 07:22 '09 u 7:22 AM 2009-12-11 07:22

Izvedba @atk implementacije za sortirane primitivne nizove može se poboljšati korištenjem .pop, a ne .shift.

 function intersect(array1, array2) { var result = []; // Don't destroy the original arrays var a = array1.slice(0); var b = array2.slice(0); var aLast = a.length - 1; var bLast = b.length - 1; while (aLast >= 0  bLast >= 0) { if (a[aLast] > b[bLast] ) { a.pop(); aLast--; } else if (a[aLast] < b[bLast] ){ b.pop(); bLast--; } else  { result.push(a.pop()); b.pop(); aLast--; bLast--; } } return result; } 

Napravio sam test koristeći jsPerf: http://bit.ly/P9FrZK . To je oko tri puta brže za korištenje .pop.

8
odgovor je dan xn. 2012-07-19 22:33 19. srpnja '12. U 22:33 sati 2012-07-19 22:33

Za nizove koji sadrže samo nizove ili brojeve, možete učiniti nešto s sortiranjem, poput nekih drugih odgovora. Za opći slučaj polja proizvoljnih objekata, mislim da ne možete izbjeći dugačak put. Slijedeće će vam dati sjecište bilo kojeg broja nizova, koji su navedeni kao parametri, za arrayIntersection :

 var arrayContains = Array.prototype.indexOf ? function(arr, val) { return arr.indexOf(val) > -1; } : function(arr, val) { var i = arr.length; while (i--) { if (arr[i] === val) { return true; } } return false; }; function arrayIntersection() { var val, arrayCount, firstArray, i, j, intersection = [], missing; var arrays = Array.prototype.slice.call(arguments); // Convert arguments into a real array // Search for common values firstArray = arrays.pop(); if (firstArray) { j = firstArray.length; arrayCount = arrays.length; while (j--) { val = firstArray[j]; missing = false; // Check val is present in each remaining array i = arrayCount; while (!missing  i--) { if ( !arrayContains(arrays[i], val) ) { missing = true; } } if (!missing) { intersection.push(val); } } } return intersection; } arrayIntersection( [1, 2, 3, "a"], [1, "a", 2], ["a", 1] ); // Gives [1, "a"]; 
7
11 дек. Odgovor je dao Tim Down 11. prosinca 2009-12-11 14:37 '09 u 14:37 2009-12-11 14:37

Moj doprinos uvjetima ES6. Općenito, on pronalazi sjecište niza s neodređenim brojem nizova koji se daju kao argumenti.

7
15 мая '16 в 15:23 2016-05-15 15:23 Odgovor je dat Redu 15. svibnja '16 u 15:23 2016-05-15 15:23

To je prilično kratko s ES2015 i setovima. Prihvaća vrijednosti tipa Array, kao što je String, i uklanja duplikate.

6
12 мая '17 в 11:59 2017-05-12 11:59 Odgovor daje SeregPie dana 12. svibnja 2006. u 11:59 2017-05-12 11:59
  • sortiranje
  • provjerite jedan po jedan iz indeksa 0, stvorite novi niz iz njega.

Nešto poput ovoga, ipak nije dobro testirano.

 function intersection(x,y){ x.sort();y.sort(); var i=j=0;ret=[]; while(i<x.length  j<y.length){ if(x[i]<y[j])i++; else if(y[j]<x[i])j++; else { ret.push(x[i]); i++,j++; } } return ret; } alert(intersection([1,2,3], [2,3,4,5])); 

PS: Algoritam namijenjen samo za brojeve i normalne nizove, sjecište arbinskih nizova objekata možda neće raditi.

6
11 дек. Odgovor je dan VAS 11.12. 2009-12-11 06:15 '09 u 6:15 am 2009-12-11 06:15

Mala postavka za najmanju ovdje ( rješenje filter / indexOf ), odnosno stvaranje indeksa vrijednosti u jednom od polja pomoću JavaScript objekta, smanjit će ga iz O (N * M) u "vjerojatno" linearno vrijeme. source1 source2

 function intersect(a, b) { var aa = {}; a.forEach(function(v) { aa[v]=1; }); return b.filter(function(v) { return v in aa; }); } 

To nije najjednostavnije rješenje (to je više kôd nego filtar + indexOf ), a nije najbrže (možda sporije za konstantni faktor od intersect_safe () ), ali izgleda kao prilično dobra ravnoteža. To je na vrlo jednostavnoj strani, dok pruža dobre performanse i ne zahtijeva unaprijed sortirane ulaze.

5
26 нояб. Odgovorite Davidu 26. studenog 2015-11-26 21:46 '15 u 21:46 2015-11-26 21:46

Uz neka ograničenja na vašim podacima, možete to učiniti u linearnom vremenu!

Za pozitivne integers : koristite niz koji mapira vrijednosti na "vidljive / nezapažene" logičke.

 function intersectIntegers(array1,array2) { var seen=[], result=[]; for (var i = 0; i < array1.length; i++) { seen[array1[i]] = true; } for (var i = 0; i < array2.length; i++) { if ( seen[array2[i]]) result.push(array2[i]); } return result; } 

Postoji slična metoda za objekte : uzmite lažan ključ, postavite ga na "true" za svaki element u nizu 1, a zatim pronađite taj ključ u elementima array2. Očistite kada završite.

 function intersectObjects(array1,array2) { var result=[]; var key="tmpKey_intersect" for (var i = 0; i < array1.length; i++) { array1[i][key] = true; } for (var i = 0; i < array2.length; i++) { if (array2[i][key]) result.push(array2[i]); } for (var i = 0; i < array1.length; i++) { delete array1[i][key]; } return result; } 

Naravno, morate biti sigurni da se ključ nije pojavio ranije, inače ćete uništiti svoje podatke ...

4
16 июля '15 в 19:13 2015-07-16 19:13 odgovor je datululun 16. srpnja '15 u 19:13 2015-07-16 19:13

Još jedan indeksirani pristup koji može obraditi neograničen broj nizova odjednom:

 // Calculate intersection of multiple array or object values. function intersect (arrList) { var arrLength = Object.keys(arrList).length; // (Also accepts regular objects as input) var index = {}; for (var i in arrList) { for (var j in arrList[i]) { var v = arrList[i][j]; if (index[v] === undefined) index[v] = 0; index[v]++; }; }; var retv = []; for (var i in index) { if (index[i] == arrLength) retv.push(i); }; return retv; }; 

Radi samo za vrijednosti koje se mogu vrednovati kao nizovi, a morate ih proslijediti kao niz, na primjer:

 intersect ([arr1, arr2, arr3...]); 

... ali prihvaća objekte transparentno kao parametar ili kao bilo koji od elemenata koji se presijecaju (uvijek vraća niz uobičajenih vrijednosti). primjeri:

 intersect ({foo: [1, 2, 3, 4], bar: {a: 2, j:4}}); // [2, 4] intersect ([{x: "hello", y: "world"}, ["hello", "user"]]); // ["hello"] 

EDIT: Upravo sam primijetio da je to, na neki način, pomalo lud.

To je: kodirao sam ga, misleći da ulazni nizovi ne mogu sadržavati ponavljanja (kao što nije prikazano u primjeru).

Ali ako se ulazni nizovi sastoje od ponavljanja, to će dovesti do netočnih rezultata. Primjer (pomoću implementacije u nastavku):

 intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]); // Expected: [ '1' ] // Actual: [ '1', '3' ] 

Srećom, to je lako popraviti dodavanjem indeksa drugog stupnja. To je:

promijeniti:

  if (index[v] === undefined) index[v] = 0; index[v]++; 

prema:

  if (index[v] === undefined) index[v] = {}; index[v][i] = true; // Mark as present in i input. 

... i:

  if (index[i] == arrLength) retv.push(i); 

prema:

  if (Object.keys(index[i]).length == arrLength) retv.push(i); 

Puni primjer:

 // Calculate intersection of multiple array or object values. function intersect (arrList) { var arrLength = Object.keys(arrList).length; // (Also accepts regular objects as input) var index = {}; for (var i in arrList) { for (var j in arrList[i]) { var v = arrList[i][j]; if (index[v] === undefined) index[v] = {}; index[v][i] = true; // Mark as present in i input. }; }; var retv = []; for (var i in index) { if (Object.keys(index[i]).length == arrLength) retv.push(i); }; return retv; }; intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]); // [ '1' ] 
4
04 марта '15 в 15:51 2015-03-04 15:51 odgovor je dat bitifet 04 ožujak '15 u 15:51 2015-03-04 15:51

Doprinijet ću onome što je za mene najbolje:

 if (!Array.prototype.intersect){ Array.prototype.intersect = function (arr1) { var r = [], o = {}, l = this.length, i, v; for (i = 0; i < l; i++) { o[this[i]] = true; } l = arr1.length; for (i = 0; i < l; i++) { v = arr1[i]; if (v in o) { r.push(v); } } return r; }; } 
3
18 мая '13 в 16:36 2013-05-18 16:36 Odgovor koji je dao Johan 18. svibnja '13 u 4:36 2013-05-18 16:36

 function intersection(A,B){ var result = new Array(); for (i=0; i<A.length; i++) { for (j=0; j<B.length; j++) { if (A[i] == B[j]  $.inArray(A[i],result) == -1) { result.push(A[i]); } } } return result; } 
3
20 сент. odgovor je dao Gabe na 20 sep. 2012-09-20 00:13 '12 u 0:13 2012-09-20 00:13

"indexOf" za IE 9.0, krom, krijesnica, opera,

  function intersection(a,b){ var rs = [], x = a.length; while (x--) b.indexOf(a[x])!=-1  rs.push(a[x]); return rs.sort(); } intersection([1,2,3], [2,3,4,5]); //Result: [2,3] 
3
28 окт. Odgovor dao je Martin Roberto Mondragon Sotel 28. listopada. 2014-10-28 20:08 '14 u 20:08 2014-10-28 20:08

2
03 окт. Odgovor je dat Vlad Bezden 03 Oct. 2016-10-03 22:51 '16 u 22:51 2016-10-03 22:51

Radi jednostavnosti:

 // Usage const intersection = allLists .reduce(intersect, allValues) .reduce(removeDuplicates, []); // Implementation const intersect = (intersection, list) => intersection.filter(item => list.some(x => x === item)); const removeDuplicates = (uniques, item) => uniques.includes(item) ? uniques : uniques.concat(item); // Example Data const somePeople = [bob, doug, jill]; const otherPeople = [sarah, bob, jill]; const morePeople = [jack, jill]; const allPeople = [...somePeople, ...otherPeople, ...morePeople]; const allGroups = [somePeople, otherPeople, morePeople]; // Example Usage const intersection = allGroups .reduce(intersect, allPeople) .reduce(removeDuplicates, []); intersection; // [jill] 

prednosti:

  • jednostavna prljavština
  • orijentiran na podatke
  • radi za bilo koji broj popisa
  • radi za proizvoljne duljine popisa
  • radi za proizvoljne vrste vrijednosti
  • radi za proizvoljni redoslijed sortiranja
  • sprema obrazac (redoslijed prvog pojavljivanja u bilo kojem nizu)
  • izlazi rano
  • sigurna memorija, osim za krivotvorenje prototipova funkcije / polja.

nedostaci:

  • veća memorija
  • veće opterećenje procesora
  • zahtijeva razumijevanje smanjenja
  • zahtijeva razumijevanje toka podataka

Ne biste to željeli koristiti za rad s 3D motorom ili kernelom, ali ako imate problema s pokretanjem u aplikaciji zasnovanoj na događajima, vaš će dizajn imati velike probleme.

2
02 февр. Odgovor daje Norguard 02. veljače. 2017-02-02 23:22 '17 u 23:22 sati 2017-02-02 23:22

Funkcionalni pristup s ES2015

Funkcionalni pristup treba uzeti u obzir uporabu čistih funkcija bez nuspojava, od kojih se svaka odnosi samo na jedan zadatak.

Ta ograničenja povećavaju sposobnost i mogućnost ponovnog korištenja uključenih funkcija.

2
11 окт. Odgovor je dat za 11. listopad. 2016-10-11 12:07 '16 u 12:07 2016-10-11 12:07
 function getIntersection(arr1, arr2){ var result = []; arr1.forEach(function(elem){ arr2.forEach(function(elem2){ if(elem === elem2){ result.push(elem); } }); }); return result; } getIntersection([1,2,3], [2,3,4,5]); // [ 2, 3 ] 
1
21 окт. odgovor dan bekzat 21. lis 2017-10-21 02:36 '17 u 2:36 am 2017-10-21 02:36

.reduce za izradu karte i .filter za pronalaženje raskrižja. delete unutar .filter omogućuje nam da tretiramo drugi niz kao da je jedinstven.

 function intersection (a, b) { var seen = a.reduce(function (h, k) { h[k] = true; return h; }, {}); return b.filter(function (k) { var exists = seen[k]; delete seen[k]; return exists; }); } 

Vjerujem da je ovaj pristup vrlo lako razumljiv. Radi u stalnom vremenu.

1
21 марта '17 в 12:19 2017-03-21 12:19 odgovor je dat Belden 21. ožujka 2006. u 12:19 2017-03-21 12:19

Evo implementacije underscore.js :

 _.intersection = function(array) { if (array == null) return []; var result = []; var argsLength = arguments.length; for (var i = 0, length = array.length; i < length; i++) { var item = array[i]; if (_.contains(result, item)) continue; for (var j = 1; j < argsLength; j++) { if (!_.contains(arguments[j], item)) break; } if (j === argsLength) result.push(item); } return result; }; 

Izvor: http://underscorejs.org/docs/underscore.html#section-62

1
30 дек. Odgovor je dat Dorian 30 Dec. 2014-12-30 03:58 '15 u 3:58 2014-12-30 03:58

Ovo je vjerojatno najjednostavnije, osim list1.filter (n => list2.includes (n))

1
03 февр. Odgovor dao Chris Lwin 3. veljače 2018-02-03 07:55 '18 u 7:55 2018-02-03 07:55
 var listA = [1,2,3,4,5,6,7]; var listB = [2,4,6,8]; var result = listA.filter(itemA=> { return listB.some(itemB => itemB === itemA); }); 
0
24 янв. odgovor dao jcmordan 24. siječnja 2017-01-24 22:12 '17 u 10:12 2017-01-24 22:12

Sljedeći kôd također uklanja duplikate:

  function intersect(x, y) { if (y.length > x.length) temp = y, y = x, x= temp; return x.filter(function (e, i, c) { return c.indexOf(e) === i; }); } 
0
01 дек. Odgovor je dan Eni 01. prosinca. 2017-12-01 16:55 '17 u 4:55 2017-12-01 16:55

Nadam se da ovo pomaže za sve verzije.

 function diffArray(arr1, arr2) { var newArr = []; var large = arr1.length>=arr2.length?arr1:arr2; var small = JSON.stringify(large) == JSON.stringify(arr1)?arr2:arr1; for(var i=0;i<large.length;i++){ var copyExists = false; for(var j =0;j<small.length;j++){ if(large[i]==small[j]){ copyExists= true; break; } } if(!copyExists) { newArr.push(large[i]); } } for(var i=0;i<small.length;i++){ var copyExists = false; for(var j =0;j<large.length;j++){ if(large[j]==small[i]){ copyExists= true; break; } } if(!copyExists) { newArr.push(small[i]); } } return newArr; } 
0
29 янв. Odgovor dao Shubham Pandey 29. siječnja 2017-01-29 17:14 '17 u 17:14 2017-01-29 17:14

Na temelju Anonovog izvrsnog odgovora, vraća sjecište dva ili više nizova.

 function arrayIntersect(arrayOfArrays) { var arrayCopy = arrayOfArrays.slice(), baseArray = arrayCopy.pop(); return baseArray.filter(function(item) { return arrayCopy.every(function(itemList) { return itemList.indexOf(item) !== -1; }); }); } 
0
26 янв. Odgovor daje Dag Sondre Hansen na 26. siječnja. 2017-01-26 11:54 '17 u 11:54 2017-01-26 11:54

Proširio sam tarulen odgovor na rad s bilo kojim brojem nizova. Također bi trebao raditi s vrijednostima koje nisu cijele.

 function intersect() { const last = arguments.length - 1; var seen={}; var result=[]; for (var i = 0; i < last; i++) { for (var j = 0; j < arguments[i].length; j++) { if (seen[arguments[i][j]]) { seen[arguments[i][j]] += 1; } else if (!i) { seen[arguments[i][j]] = 1; } } } for (var i = 0; i < arguments[last].length; i++) { if ( seen[arguments[last][i]] === last) result.push(arguments[last][i]); } return result; } 
0
19 сент. odgovor je dan gabe appletonu 19. rujna 2016-09-19 17:34 '16 u 17:34 2016-09-19 17:34
  • 1
  • 2