Sprawdź, czy każdy element w jednej tablicy znajduje się w drugiej macierzy.

Question

Mam dwie tablice i chcę sprawdzić, czy każdy element w arr2 jest w arr1. Jeśli wartość elementu zostanie powtórzona w arr2, musi być równa arr1 tyle razy. Jaki jest najlepszy sposób na zrobienie tego?

arr1 = [1, 2, 3, 4] 
arr2 = [1, 2] 

checkSuperbag(arr1, arr2) 
> true //both 1 and 2 are in arr1 

arr1 = [1, 2, 3, 4] 
arr2 = [1, 2, 5] 

checkSuperbag(arr1, arr2) 
> false //5 is not in arr1 

arr1 = [1, 2, 3] 
arr2 = [1, 2, 3, 3] 

checkSuperbag(arr1, arr2) 
> false //3 is not in arr1 twice 

Answer 1

Jedną opcją jest posortowanie dwóch tablic, a następnie przemieszczenie obu elementów, porównywanie. Jeśli element znajdujący się w worku kandydata nie znajduje się w super-worku, ten pierwszy nie jest workiem zbiorczym. Sortowanie to zazwyczaj O (n * log (n)), a porównanie to O (max (s, t)), gdzie s i t są rozmiarami macierzy, dla całkowitej złożoności czasu O (m * log (m)), gdzie m = maksimum (s, t).

function superbag(sup, sub) { 
    sup.sort(); 
    sub.sort(); 
    var i, j; 
    for (i=0,j=0; i<sup.length && j<sub.length;) { 
     if (sup[i] < sub[j]) { 
      ++i; 
     } else if (sup[i] == sub[j]) { 
      ++i; ++j; 
     } else { 
      // sub[j] not in sup, so sub not subbag 
      return false; 
     } 
    } 
    // make sure there are no elements left in sub 
    return j == sub.length; 
} 

Jeśli elementy w rzeczywistym kodzie są liczbami całkowitymi, można użyć specjalnego przeznaczenia całkowitą algorytmu sortowania (np radix sort) dla ogólnego O (max (S, T)) Czas złożoność, choć jeśli torby są małe, wbudowany Array.sort prawdopodobnie będzie działał szybciej niż niestandardowe sortowanie liczb całkowitych.

Rozwiązaniem o potencjalnie mniejszej złożoności czasowej jest stworzenie typu torby. Worki typu Integer są szczególnie łatwe. Odwróć istniejące tablice dla toreb: utwórz obiekt lub tablicę z liczbami całkowitymi jako kluczami i liczbę powtórzeń dla wartości. Korzystanie z tablicy nie powoduje marnowania miejsca, tworząc jako arrays are sparse in Javascript. Możesz używać operacji workowania do kontroli sub-bagów lub super-bagów. Na przykład odejmij super od drugiego kandydata i sprawdź, czy wynik nie jest pusty.Alternatywnie, operacja contains powinna być O (1) (lub ewentualnie O (log (n))), więc zapętlić się nad kandydatem do worka podrzędnego i przetestować, czy opakowanie super-worka przekracza osłonę worka podrzędnego dla każdej z torebek element powinien być O (n) lub O (n * log (n)).

Następujące produkty nie zostały przetestowane. Wdrożenie isInt pozostawione jako ćwiczenie.

function IntBag(from) { 
    if (from instanceof IntBag) { 
     return from.clone(); 
    } else if (from instanceof Array) { 
     for (var i=0; i < from.length) { 
      this.add(from[i]); 
     } 
    } else if (from) { 
     for (p in from) { 
      /* don't test from.hasOwnProperty(p); all that matters 
       is that p and from[p] are ints 
      */ 
      if (isInt(p) && isInt(from[p])) { 
       this.add(p, from[p]); 
      } 
     } 
    } 
} 
IntBag.prototype=[]; 
IntBag.prototype.size=0; 
IntBag.prototype.clone = function() { 
    var clone = new IntBag(); 
    this.each(function(i, count) { 
     clone.add(i, count); 
    }); 
    return clone; 
}; 
IntBag.prototype.contains = function(i) { 
    if (i in this) { 
     return this[i]; 
    } 
    return 0; 
}; 
IntBag.prototype.add = function(i, count) { 
    if (!count) { 
     count = 1; 
    } 
    if (i in this) { 
     this[i] += count; 
    } else { 
     this[i] = count; 
    } 
    this.size += count; 
}; 
IntBag.prototype.remove = function(i, count) { 
    if (! i in this) { 
     return; 
    } 
    if (!count) { 
     count = 1; 
    } 
    this[i] -= count; 
    if (this[i] > 0) { 
     // element is still in bag 
     this.size -= count; 
    } else { 
     // remove element entirely 
     this.size -= count + this[i]; 
     delete this[i]; 
    } 
}; 
IntBag.prototype.each = function(f) { 
    var i; 
    foreach (i in this) { 
     f(i, this[i]); 
    } 
}; 
IntBag.prototype.find = function(p) { 
    var result = []; 
    var i; 
    foreach (i in this.elements) { 
     if (p(i, this[i])) { 
      return i; 
     } 
    } 
    return null; 
}; 
IntBag.prototype.sub = function(other) { 
    other.each(function(i, count) { 
     this.remove(i, count); 
    }); 
    return this; 
}; 
IntBag.prototype.union = function(other) { 
    var union = this.clone(); 
    other.each(function(i, count) { 
     if (union.contains(i) < count) { 
      union.add(i, count - union.contains(i)); 
     } 
    }); 
    return union; 
}; 
IntBag.prototype.intersect = function(other) { 
    var intersection = new IntBag(); 
    this.each(function (i, count) { 
     if (other.contains(i)) { 
      intersection.add(i, Math.min(count, other.contains(i))); 
     } 
    }); 
    return intersection; 
}; 
IntBag.prototype.diff = function(other) { 
    var mine = this.clone(); 
    mine.sub(other); 
    var others = other.clone(); 
    others.sub(this); 
    mine.union(others); 
    return mine; 
}; 
IntBag.prototype.subbag = function(super) { 
    return this.size <= super.size 
     && null !== this.find(
      function (i, count) { 
       return super.contains(i) < this.contains(i); 
      })); 
}; 

Patrz także „comparing javascript arrays” dla przykładowej implementacji zbioru obiektów, należy zawsze chcą uniemożliwić powtórzenie elementów.

Answer 2

Czy potrzebujesz obsługi przeglądarek Crummy? Jeśli nie, funkcja every powinna to ułatwić.

Jeśli arr1 jest rozszerzeniem ARR2, wtedy każdy członek ARR2 musi być obecny w arr1

var isSuperset = arr2.every(function(val) { return arr1.indexOf(val) >= 0; }); 

Oto fiddle

EDIT

Więc definiowania rozszerzeniem takiego że dla każdego elementu w arr2 występuje on w arr1 tyle samo razy? Myślę filter pomoże to zrobisz (zgarnij podkładkę z poprzedniego MDN linku do obsługi starszych przeglądarek):

var isSuperset = arr2.every(function (val) { 
    var numIn1 = arr1.filter(function(el) { return el === val; }).length; 
    var numIn2 = arr2.filter(function(el) { return el === val; }).length; 
    return numIn1 === numIn2; 
}); 

Updated Fiddle

END EDIT

---

Jeżeli chcesz aby obsługiwać starsze przeglądarki, powyższy odnośnik MDN ma podkładkę, którą można dodać, a którą tu odtwarzam dla Twojej wygody:

if (!Array.prototype.every) 
{ 
    Array.prototype.every = function(fun /*, thisp */) 
    { 
    "use strict"; 

    if (this == null) 
     throw new TypeError(); 

    var t = Object(this); 
    var len = t.length >>> 0; 
    if (typeof fun != "function") 
     throw new TypeError(); 

    var thisp = arguments[1]; 
    for (var i = 0; i < len; i++) 
    { 
     if (i in t && !fun.call(thisp, t[i], i, t)) 
     return false; 
    } 

    return true; 
    }; 
} 

EDIT

Należy zauważyć, że będzie to O (N) algorytm, aby uniknąć prowadzenia go na dużej macierzy.

Answer 3

Szybkie rozwiązanie w tym przypadku wymaga dwóch tablic, jeśli b jest dłuższy niż nie może być ustawiony jako super, więc zwraca false. Następnie przeprowadź pętlę przez b, aby zobaczyć, czy zawiera element. Jeśli tak, usuń go z a i przejdź dalej, jeśli nie zwróci false. Najgorszy scenariusz jest taki, że jeśli b jest podzbiorem, to czas będzie wynosił b.length.

function isSuper(a,b){ 
    var l=b.length,i=0,c; 
    if(l>a.length){return false} 
    else{ 
    for(i;i<l;i++){ 
     c=a.indexOf(b[i]); 
     if(c>-1){ 
     a.splice(c,1); 
     } 
     else{return false} 
    } 
    return true; 
    } 
} 

ta zakłada, że ​​nakłady nie zawsze będzie w porządku i jeśli a jest 1,2,3 i b jest 3,2,1 będzie jeszcze powrócić prawda.

Answer 4

Nikt jeszcze nie opublikował funkcji rekurencyjnej, a te są zawsze zabawne. Nazwij to jak arr1.containsArray(arr2).

Demo: http://jsfiddle.net/ThinkingStiff/X9jed/

Array.prototype.containsArray = function (array /*, index, last*/) { 

    if(arguments[1]) { 
     var index = arguments[1], last = arguments[2]; 
    } else { 
     var index = 0, last = 0; this.sort(); array.sort(); 
    }; 

    return index == array.length 
     || (last = this.indexOf(array[index], last)) > -1 
     && this.containsArray(array, ++index, ++last); 

}; 

Answer 5

Wykorzystanie obiektów (Odczyt: Tabele hash) zamiast sortowania powinna zmniejszyć zamortyzowanego złożoność O (m + n):

function bagContains(arr1, arr2) { 
    var o = {} 
    var result = true; 

    // Count all the objects in container 
    for(var i=0; i < arr1.length; i++) { 
     if(!o[arr1[i]]) { 
      o[arr1[i]] = 0; 
     } 
     o[arr1[i]]++; 
    } 

    // Subtract all the objects in containee 
    // And exit early if possible 
    for(var i=0; i < arr2.length; i++) { 
     if(!o[arr2[i]]) { 
      o[arr2[i]] = 0; 
     } 
     if(--o[arr2[i]] < 0) { 
      result = false; 
      break; 
     } 
    } 

    return result; 
} 

console.log(bagContains([1, 2, 3, 4], [1, 3])); 
console.log(bagContains([1, 2, 3, 4], [1, 3, 3])); 
console.log(bagContains([1, 2, 3, 4], [1, 3, 7])); 

co daje true, false, false.

Answer 6

Jeśli chodzi o inne podejście, możesz wykonać następujące czynności;

function checkIn(a,b){ 
 
    return b.every(function(e){ 
 
        return e === this.splice(this.indexOf(e),1)[0]; 
 
       }, a.slice()); // a.slice() is the "this" in the every method 
 
} 
 

 
var arr1 = [1, 2, 3, 4], 
 
    arr2 = [1, 2], 
 
    arr3 = [1,2,3,3]; 
 
console.log(checkIn(arr1,arr2)); 
 
console.log(checkIn(arr1,arr3));

Answer 7

mała wersja:

function checkSuperbag(arr1, arr2) { 
    return !!~arr2.join('').indexOf(arr1.join('')) 
} 

Answer 8

Jeśli arr2 jest podzbiorem arr1, następnie Length of set(arr1 + arr2) == Length of set(arr1)

var arr1 = [1, 'a', 2, 'b', 3]; 
var arr2 = [1, 2, 3]; 

Array.from(new Set(arr1)).length == Array.from(new Set(arr1.concat(arr2))).length 

Answer 9

Oto moje rozwiązanie:

Array.prototype.containsIds = function (arr_ids) { 
    var status = true; 
    var current_arr = this; 
    arr_ids.forEach(function(id) { 
     if(!current_arr.includes(parseInt(id))){ 
      status = false; 
      return false; // exit forEach 
     } 
    }); 
    return status; 
}; 

// Examples 
[1,2,3].containsIds([1]); // true 
[1,2,3].containsIds([2,3]); // true 
[1,2,3].containsIds([3,4]); // false