Ein array ist Teilmenge des anderen array

Wie kann ich effizient überprüfen, um zu sehen, ob alle Elemente in ein integer-array sind Teilmenge aller Elemente eines anderen Array in java? Zum Beispiel [33 11 23] ist Untergruppe von [11 23 33 42]. Vielen Dank im Voraus.

InformationsquelleAutor MTT | 2013-03-26
  1. 3

    Machen HashSet aus der Obermenge array. Überprüfen Sie, ob jedes Element der Teilmenge array enthalten sind in der HashSet. Dies ist eine sehr schnelle operation.

    • Sie müssen nicht wählen Sie die "größer" / "kleiner" - arrays. Sie Holen Sie nach der angeblich die Teilmenge der anderen.
    • C Feste Terminologie
    InformationsquelleAutor Patashu
  2. 8

    Wenn Sie nicht gebunden an die Verwendung von Arrays, Java-collection hat die containsAll Methode:

    boolean isSubset = bigList.containsAll(smallList);

    Dieser wird genau das tun, was Sie wollen, effizient.

    InformationsquelleAutor mwielbut
  3. 3

    angenommen, Sie möchten prüfen, A ist Teilmenge von B jedes element von B in einen hash, dann iterieren über Elemente in A, die alle vorhanden sein müssen, die hash -

    • +1 - Für große Eingänge, wird dies die effizienteste sein.
    InformationsquelleAutor marcadian
  4. 1

    Ich kam mit zwei anderen Lösung

    Eingang:
    int mainArray[] = { 1, 2, 3, 2, 5, 6, 2 }, subArray[] = { 2, 2, 2 };

    • erste Lösung iteriert über die beiden arrays enthalten ist und vergleichen Sie,
      main[i] = -1 wird verwendet, um zu vermeiden, sich wiederholende Elemente enthalten wieder

      void findIfArrayIsASubset(int[] main, int[] sub) {
int count = 0;
for (int i = 0; i < main.length; i++) {
    for (int j = 0; j < sub.length; j++) {
        if (main[i] == sub[j]) {
            main[i] = -1;
            count++;
            break;
        }
    }
}
if (count == sub.length)
    System.out.println("is a subset");
else
    System.out.println("is not a subset");
}

    • zweite Lösung verwendet hashmap mit den Tasten von 1....9 und Wert als 0,

      als Nächstes werden wir iterieren über Haupt-array und +1 jeweiligen Wert

      als Nächstes werden wir iterieren über sub-array und die -1 jeweiligen Wert

      neben comapre Summe der Werte der hashmap zu Unterschied in der Länge der beiden Arrays

      void findIfArrayIsASubset(int[] main, int[] sub) {
Map<Integer, Integer> mainMap = new HashMap<Integer, Integer>();
for (int i = 0; i < 10; i++) {
    mainMap.put(i, 0);
}
for (int i = 0; i < main.length; i++) {
    mainMap.put(main[i], mainMap.get(main[i]) + 1);
}
for (int i = 0; i < sub.length; i++) {
    mainMap.put(main[i], mainMap.get(main[i]) - 1);
}
String output = mainMap.values().stream().reduce(0, Integer::sum).compareTo(main.length - sub.length) == 0
        ? "is a subset" : "not a subset";
System.out.println(output);
}
    InformationsquelleAutor ericdemo07
  5. 0

    Der äußeren Schleife nimmt alle der Elemente von arr2[] eins nach dem anderen. Die innere Schleife wird Linear durchsucht, um das element wieder durch äußere Schleife. Wenn alle Elemente gefunden werden, dann true zurück, sonst false zurück.

    boolean checkIsSubset(int arr1[], int arr2[]){

        int m=arr1.length,  n=arr2.length;
    int i = 0;
    int j = 0;
    for (i=0; i<n; i++){
        for (j = 0; j<m; j++){
           if(arr2[i] == arr1[j])
              break;
        }
        if (j == m)
           return false;
    }
    return true;
}

    Warum tun binäre Suche nach dem Sortieren??
    Da beide arrays verfügbar sein wird in sortierter form, können wir nur verwenden zwei Zeiger wie folgt:-

    boolean isSubset(int arr1[], int arr2[], int m, int n){

    int i = 0, j = 0;
quickSort(arr1, 0, m-1);
quickSort(arr2, 0, n-1);
while( i < n && j < m )
{
    if( arr1[j] <arr2[i] )
        j++;
    else if( arr1[j] == arr2[i] )
    {
        j++;
        i++;
    }
    else if( arr1[j] > arr2[i] )
        return false;
}

if( i < n )
    return false;
else
    return true;

    }

    InformationsquelleAutor
  6. 0

    Sortieren, sowohl die arrays und überprüfen Sie alle Elemente in der kleineren Felder vorhanden sind, in larget-array. Dies ist ohne Verwendung von zusätzlichen Platz.

    Wenn nicht, benutze hasmap wie schon jemand vorgeschlagen.

    InformationsquelleAutor David Prun
  7. -1

    Diese überprüft, ob alle Elemente der möglichen Teilmenge fehlt von den größeren array. Wenn es ist, es ist nicht eine Teilmenge:

    boolean isSubset(int[] a1, int[] a2) {
    a2 = Arrays.copyOf(a2, a2.length);
    Arrays.sort(a2);
    for(int e : a1) {
        if (Arrays.binarySearch(a2, e) < 0) {
            return false;
        }
    }
    return true;
}
    InformationsquelleAutor Evgeniy Dorofeev
Schreibe einen Kommentar