javascriptで配列交差を実装するための最も単純でライブラリのないコードは何ですか? 書きたい
intersection([1,2,3], [2,3,4,5])
そして得る
[2, 3]
601804 次
39 に答える
1595
と の組み合わせを使用しArray.prototype.filterますArray.prototype.includes。
const filteredArray = array1.filter(value => array2.includes(value));
Array.prototype.indexOf矢印機能の有無にかかわらず、古いブラウザーの場合:
var filteredArray = array1.filter(function(n) {
return array2.indexOf(n) !== -1;
});
注意！と の両方が を使用して配列内の要素.includesを内部的に比較するため、配列にオブジェクトが含まれている場合は、オブジェクト参照のみが比較されます (その内容は比較されません)。独自の比較ロジックを指定する場合は、代わりに を使用してください。.indexOf===Array.prototype.some
于 2009-12-11T03:08:37.137 に答える
160
特に入力がソートされていると仮定できる場合は、破壊的が最も単純に見えます。
/* destructively finds the intersection of
* two arrays in a simple fashion.
*
* PARAMS
* a - first array, must already be sorted
* b - second array, must already be sorted
*
* NOTES
* State of input arrays is undefined when
* the function returns. They should be
* (prolly) be dumped.
*
* Should have O(n) operations, where n is
* n = MIN(a.length, b.length)
*/
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 /* they're equal */
{
result.push(a.shift());
b.shift();
}
}
return result;
}
インデックスを追跡する必要があるため、非破壊的なものはもっと複雑でなければなりません。
/* finds the intersection of
* two arrays in a simple fashion.
*
* PARAMS
* a - first array, must already be sorted
* b - second array, must already be sorted
*
* NOTES
*
* Should have O(n) operations, where n is
* n = MIN(a.length(), b.length())
*/
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 /* they're equal */
{
result.push(a[ai]);
ai++;
bi++;
}
}
return result;
}
于 2009-12-11T03:45:00.573 に答える
103
お使いの環境がECMAScript 6 Setをサポートしている場合、シンプルで効率的と思われる 1 つの方法 (仕様のリンクを参照):
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);
}
短くなりますが、読みにくくなります (追加の交差を作成しない場合もSet):
function intersect(a, b) {
var setB = new Set(b);
return [...new Set(a)].filter(x => setB.has(x));
}
セットを使用する場合、個別の値のみが取得されるため、 にnew Set([1, 2, 3, 3]).size評価されることに注意してください3。
于 2016-05-05T03:21:26.750 に答える
71
Underscore.jsまたはlodash.js の使用
_.intersection( [0,345,324] , [1,0,324] ) // gives [0,324]
于 2016-09-29T07:51:36.140 に答える
18
ES6 用語での私の貢献。一般に、引数として提供された不定数の配列と配列の共通部分を見つけます。
Array.prototype.intersect = function(...a) {
return [this,...a].reduce((p,c) => p.filter(e => c.includes(e)));
}
var arrs = [[0,2,4,6,8],[4,5,6,7],[4,6]],
arr = [0,1,2,3,4,5,6,7,8,9];
document.write("<pre>" + JSON.stringify(arr.intersect(...arrs)) + "</pre>");于 2016-05-15T12:23:13.920 に答える
12
連想配列を使用するだけではどうですか?
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;
}
編集：
// 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;
}
于 2009-12-11T04:22:33.570 に答える
10
プリミティブのソートされた配列に対する@atkの実装のパフォーマンスは、.shiftではなく.popを使用することで改善できます。
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 /* they're equal */ {
result.push(a.pop());
b.pop();
aLast--;
bLast--;
}
}
return result;
}
jsPerfを使用してベンチマークを作成しました：http：//bit.ly/P9FrZK。.popを使用する方が約3倍高速です。
于 2012-07-19T19:33:22.907 に答える
9
- 並べ替え
- インデックス 0 から 1 つずつチェックし、そこから新しい配列を作成します。
このようなものですが、よくテストされていません。
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: このアルゴリズムは数値と通常の文字列のみを対象としているため、任意のオブジェクト配列の交差は機能しない可能性があります。
于 2009-12-11T03:15:42.363 に答える
9
複数の配列の交差を処理する必要がある場合:
const intersect = (a1, a2, ...rest) => {
const a12 = a1.filter(value => a2.includes(value))
if (rest.length === 0) { return a12; }
return intersect(a12, ...rest);
};
console.log(intersect([1,2,3,4,5], [1,2], [1, 2, 3,4,5], [2, 10, 1])) 于 2018-03-09T04:41:38.137 に答える
9
jQuery の使用:
var a = [1,2,3];
var b = [2,3,4,5];
var c = $(b).not($(b).not(a));
alert(c);
于 2013-12-25T07:20:49.147 に答える
6
文字列または数値のみを含む配列の場合、他の回答のいくつかに従って、並べ替えで何かを行うことができます。任意のオブジェクトの配列の一般的なケースでは、長い道のりを避けることはできないと思います。以下は、パラメータとして に提供された任意の数の配列の共通部分を示します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"];
于 2009-12-11T11:37:28.023 に答える
5
一度に任意の数の配列を処理できる別のインデックス付きアプローチ:
// 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;
};
文字列として評価できる値に対してのみ機能し、次のような配列として渡す必要があります。
intersect ([arr1, arr2, arr3...]);
...しかし、オブジェクトをパラメーターとして、または交差する要素のいずれかとして透過的に受け入れます (常に共通の値の配列を返します)。例:
intersect ({foo: [1, 2, 3, 4], bar: {a: 2, j:4}}); // [2, 4]
intersect ([{x: "hello", y: "world"}, ["hello", "user"]]); // ["hello"]
編集:これは、ある意味で少しバグがあることに気付きました。
つまり、入力配列自体に繰り返しを含めることはできないと考えてコーディングしました（提供された例には含まれていません）。
しかし、入力配列に繰り返しが含まれていると、間違った結果が生成されます。例 (以下の実装を使用):
intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]);
// Expected: [ '1' ]
// Actual: [ '1', '3' ]
幸いなことに、これは第 2 レベルのインデックスを追加するだけで簡単に修正できます。あれは：
変化する：
if (index[v] === undefined) index[v] = 0;
index[v]++;
に：
if (index[v] === undefined) index[v] = {};
index[v][i] = true; // Mark as present in i input.
...と：
if (index[i] == arrLength) retv.push(i);
に：
if (Object.keys(index[i]).length == arrLength) retv.push(i);
完全な例:
// 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' ]
于 2015-03-04T12:51:24.087 に答える
4
データにいくつかの制限があるため、線形時間で実行できます!
正の整数の場合: 値を「表示/非表示」ブール値にマッピングする配列を使用します。
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;
}
オブジェクトにも同様の手法があります。ダミー キーを取得し、array1 の各要素に対して「true」に設定してから、array2 の要素でこのキーを探します。終わったら掃除。
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;
}
もちろん、キーが以前に表示されていないことを確認する必要があります。そうしないと、データが破壊されます...
于 2015-07-16T16:13:36.903 に答える
3
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;
}
于 2012-09-19T21:13:32.387 に答える
2
ES2015 による機能的アプローチ
関数型のアプローチでは、副作用のない純粋な関数のみを使用することを検討する必要があります。これらの関数はそれぞれ 1 つのジョブのみに関係しています。
これらの制限により、関連する関数の構成可能性と再利用可能性が向上します。
// small, reusable auxiliary functions
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const apply = f => x => f(x);
// intersection
const intersect = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? true
: false
) (xs);
};
// mock data
const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
// run it
console.log( intersect(xs) (ys) );Setルックアップのパフォーマンスが有利なネイティブ型が使用されることに注意してください。
重複を避ける
明らかに、最初のアイテムから繰り返し発生するアイテムArrayは保持されますが、2 番目のアイテムArrayは重複排除されます。これは、望ましい動作である場合とそうでない場合があります。一意の結果が必要な場合はdedupe、最初の引数に適用するだけです。
// auxiliary functions
const apply = f => x => f(x);
const comp = f => g => x => f(g(x));
const afrom = apply(Array.from);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
// intersection
const intersect = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? true
: false
) (xs);
};
// de-duplication
const dedupe = comp(afrom) (createSet);
// mock data
const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
// unique result
console.log( intersect(dedupe(xs)) (ys) );任意の数のArrays の交点を計算します
任意の数の の共通部分を計算したい場合は、 でArray構成intersectするだけfoldlです。便利な関数を次に示します。
// auxiliary functions
const apply = f => x => f(x);
const uncurry = f => (x, y) => f(x) (y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const foldl = f => acc => xs => xs.reduce(uncurry(f), acc);
// intersection
const intersect = xs => ys => {
const zs = createSet(ys);
return filter(x => zs.has(x)
? true
: false
) (xs);
};
// intersection of an arbitrarily number of Arrays
const intersectn = (head, ...tail) => foldl(intersect) (head) (tail);
// mock data
const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
const zs = [0,1,2,3,4,5,6];
// run
console.log( intersectn(xs, ys, zs) );于 2016-10-11T09:07:18.443 に答える
1
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;
};
ソース: http://underscorejs.org/docs/underscore.html#section-62
于 2014-12-30T00:58:17.283 に答える
0
任意の数の配列で動作するように、tarulen の回答を拡張しました。また、整数以外の値でも機能するはずです。
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;
}
于 2016-09-19T14:34:22.487 に答える
-1
coffeescript の N 配列の交差
getIntersection: (arrays) ->
if not arrays.length
return []
a1 = arrays[0]
for a2 in arrays.slice(1)
a = (val for val in a1 when val in a2)
a1 = a
return a1.unique()
于 2013-04-18T15:47:00.567 に答える
-1
これがすべてのバージョンで役立つことを願っています。
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;
}
于 2017-01-29T14:14:27.540 に答える
-1
これは私が使用している非常に素朴な実装です。これは非破壊的であり、全体を複製しないようにもします。
Array.prototype.contains = function(elem) {
return(this.indexOf(elem) > -1);
};
Array.prototype.intersect = function( array ) {
// this is naive--could use some optimization
var result = [];
for ( var i = 0; i < this.length; i++ ) {
if ( array.contains(this[i]) && !result.contains(this[i]) )
result.push( this[i] );
}
return result;
}
于 2011-12-16T16:17:04.470 に答える
-2
効率についてではありませんが、簡単に理解できます。これは、セットの和集合と交差の例です。セットの配列とセットのセットを処理します。
http://jsfiddle.net/zhulien/NF68T/
// process array [element, element...], if allow abort ignore the result
function processArray(arr_a, cb_a, blnAllowAbort_a)
{
var arrResult = [];
var blnAborted = false;
var intI = 0;
while ((intI < arr_a.length) && (blnAborted === false))
{
if (blnAllowAbort_a)
{
blnAborted = cb_a(arr_a[intI]);
}
else
{
arrResult[intI] = cb_a(arr_a[intI]);
}
intI++;
}
return arrResult;
}
// process array of operations [operation,arguments...]
function processOperations(arrOperations_a)
{
var arrResult = [];
var fnOperationE;
for(var intI = 0, intR = 0; intI < arrOperations_a.length; intI+=2, intR++)
{
var fnOperation = arrOperations_a[intI+0];
var fnArgs = arrOperations_a[intI+1];
if (fnArgs === undefined)
{
arrResult[intR] = fnOperation();
}
else
{
arrResult[intR] = fnOperation(fnArgs);
}
}
return arrResult;
}
// return whether an element exists in an array
function find(arr_a, varElement_a)
{
var blnResult = false;
processArray(arr_a, function(varToMatch_a)
{
var blnAbort = false;
if (varToMatch_a === varElement_a)
{
blnResult = true;
blnAbort = true;
}
return blnAbort;
}, true);
return blnResult;
}
// return the union of all sets
function union(arr_a)
{
var arrResult = [];
var intI = 0;
processArray(arr_a, function(arrSet_a)
{
processArray(arrSet_a, function(varElement_a)
{
// if the element doesn't exist in our result
if (find(arrResult, varElement_a) === false)
{
// add it
arrResult[intI] = varElement_a;
intI++;
}
});
});
return arrResult;
}
// return the intersection of all sets
function intersection(arr_a)
{
var arrResult = [];
var intI = 0;
// for each set
processArray(arr_a, function(arrSet_a)
{
// every number is a candidate
processArray(arrSet_a, function(varCandidate_a)
{
var blnCandidate = true;
// for each set
processArray(arr_a, function(arrSet_a)
{
// check that the candidate exists
var blnFoundPart = find(arrSet_a, varCandidate_a);
// if the candidate does not exist
if (blnFoundPart === false)
{
// no longer a candidate
blnCandidate = false;
}
});
if (blnCandidate)
{
// if the candidate doesn't exist in our result
if (find(arrResult, varCandidate_a) === false)
{
// add it
arrResult[intI] = varCandidate_a;
intI++;
}
}
});
});
return arrResult;
}
var strOutput = ''
var arrSet1 = [1,2,3];
var arrSet2 = [2,5,6];
var arrSet3 = [7,8,9,2];
// return the union of the sets
strOutput = union([arrSet1, arrSet2, arrSet3]);
alert(strOutput);
// return the intersection of 3 sets
strOutput = intersection([arrSet1, arrSet2, arrSet3]);
alert(strOutput);
// of 3 sets of sets, which set is the intersecting set
strOutput = processOperations([intersection,[[arrSet1, arrSet2], [arrSet2], [arrSet2, arrSet3]]]);
alert(strOutput);
于 2014-04-03T07:42:13.120 に答える
-5
「filter」と「indexOf」は、IE の配列ではサポートされていません。これはどう：
var array1 = [1, 2, 3];
var array2 = [2, 3, 4, 5];
var intersection = [];
for (i in array1) {
for (j in array2) {
if (array1[i] == array2[j]) intersection.push(array1[i]);
}
}
于 2009-12-11T05:42:33.890 に答える