Verificare se ogni elemento in un array si trova in un secondo array

Question

Ho due array e voglio verificare se ogni elemento in arr2 è in arr1. Se il valore di un elemento viene ripetuto in arr2, è necessario che sia in arr1 un numero uguale di volte. Qual è il modo migliore per farlo?

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

Un'opzione consiste nell'ordinare i due array, quindi attraversarli entrambi, confrontando gli elementi. Se un elemento nel sub-bag candidate non viene trovato nel super-bag, il primo non è un sub-bag. L'ordinamento è generalmente O (n * log (n)) e il confronto è O (max (s, t)), dove s e t sono le dimensioni dell'array, per una complessità temporale totale di O (m * log (m)), dove m = max (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; 
} 

Se gli elementi del codice vero e proprio sono numeri interi, è possibile utilizzare un algoritmo di ordinamento per un fine particolare intero (come radix sort) per un O complessiva (max (s, t)) Tempo di complessità, ma se il i sacchi sono piccoli, il Array.sort integrato probabilmente funzionerà più velocemente di un ordinamento di numeri interi personalizzati.

Una soluzione con una minore complessità temporale è la creazione di un tipo di borsa. I sacchetti interi sono particolarmente facili. Capovolgi gli array esistenti per i sacchi: crea un oggetto o un array con gli interi come chiavi e un conteggio delle ripetizioni per i valori. L'utilizzo di un array non spreca spazio creando come arrays are sparse in Javascript. È possibile utilizzare le operazioni della borsa per i controlli sub-bag o super-bag. Ad esempio, sottrarre il super dal sub candidato e verificare se il risultato non è vuoto.In alternativa, l'operazione contains deve essere O (1) (o possibilmente O (log (n))), quindi eseguire il looping sul sub-bag candidate e testare se il contenimento super-bag supera il contenimento della sottocasco per ogni sottocasco l'elemento dovrebbe essere O (n) o O (n * log (n)).

Quanto segue non è stato verificato. L'implementazione di isInt è stata lasciata come esercizio.

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); 
      })); 
}; 

Vedere anche "comparing javascript arrays" per un esempio di implementazione di un insieme di oggetti, si dovrebbe mai desiderare di non consentire la ripetizione di elementi.

Answer 2

Devi supportare browser scadenti? In caso contrario, la funzione every dovrebbe semplificare la procedura.

Se arr1 è un superset di arr2, quindi ogni membro arr2 deve essere presente in arr1

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

Ecco un fiddle

EDIT

Così si sta definendo superset tale che per ogni elemento in arr2, si verifica in arr1 lo stesso numero di volte? Penso filter vi aiuterà a farlo (afferrare lo spessore dal link precedente MDN per supportare i browser più vecchi):

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

FINE EDIT

---

Se si vuole per supportare i browser più vecchi, il link MDN sopra ha uno spessore che è possibile aggiungere, che riproduco qui per comodità:

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

noti che questa sarà una O (N 2 ) algoritmo, quindi evitare l'esecuzione su grandi array.

Answer 3

La soluzione rapida qui richiede due array se b è più lungo di quanto non possa essere un super set, quindi restituire false. Quindi fai un loop su b per vedere se a contiene l'elemento. Se è così cancellalo da a e vai avanti se non restituisci falso. Lo scenario peggiore è se b è un sottoinsieme, quindi il tempo sarà 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; 
    } 
} 

Ciò presuppone che gli ingressi non saranno sempre in ordine e se è a1,2,3 e b è 3,2,1 sarà ancora restituire true.

Answer 4

Nessuno ha ancora pubblicato una funzione ricorsiva e quelli sono sempre divertenti. Chiamalo come 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

Uso di oggetti (leggi: le tabelle hash) in vece di smistamento dovrebbe ridurre la complessità ammortizzato a 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])); 

che produce true, false, false.

Answer 6

Per quanto riguarda un altro approccio si può fare come segue;

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

versione piccola:

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

Answer 8

Se arr2 è sottoinsieme di arr1, poi 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

Ecco la mia soluzione:

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