Java, um herauszufinden, ob ein Array eine Teilmenge eines anderen ist

Nov 24 2020

Ich habe Probleme herauszufinden, ob sich eine bestimmte Anzahl von Zahlen in einem anderen Array befindet. Das erste Array generiert 10 Zufallszahlen und im zweiten Array errät der Benutzer 5 Zahlen. Ich versuche herauszufinden, ob der Benutzer irgendwelche Sequenzen erraten hat Schleifen, um herauszufinden, ob die Anzahl der Benutzereingaben in einer der Zahlen von 1 bis 5 im Array von 10 enthalten ist. Andernfalls werden die Zahlen 2 bis 6 usw. überprüft. Wenn das Programm beispielsweise die folgenden Gewinnzahlen hatte: 23 56 67 06 43 22 59 24 90 66 und vom Benutzer eingegeben: 01 06 43 22 89. Ich behalte den Index immer wieder aus den Grenzen heraus. Wie behebe ich das?

    // to check if user guessed a sequence
    
    boolean guessed = false;
    int counter = 0;
    int i , j = 0;
    
    for (i = 4; i < numbers.length; i++) {    // users numbers
        
        for ( j = 4; j < lottery.length; j++) {  // first 5 numbers from array 
            
            if ( lottery[i] == numbers[j]) {
                break;
            }
            if ( j == i) {
                guessed = true;
            }
        }
    }

Antworten

1 AlexRudenko Nov 24 2020 at 20:50

Es scheint, dass eine ähnliche Methode String::indexOfin dieser Aufgabe für die Arrays implementiert werden sollte, die versuchen, einen Index eines Subarrays zu finden int indexOf(int[] search, int[] input).

Außerdem muss möglicherweise nach allen möglichen Subarrays des searchSubarrays ( lottery) gesucht werden . Daher sollte die erwähnte Methode erweitert werden, um nach einem Unterbereich des searchArguments zu suchen :int indexOf(int[] search, int[] input)

Eine einfache Implementierung wäre:

static int indexOf(int search[], int from, int to, int[] input) {
    if (null == search || null == input || search.length > input.length) {
        return -1;
    }
    
    for (int i = 0, n = input.length - (to - from); i <= n; i++) {
        boolean found = true;
        for (int j = from; found && j < to; j++) {
            if (input[i + j - from] != search[j]) {
                found = false;
            }
        }
        if (found) {
            return i;
        }
    }
    return -1;
}

Die Breiten und entsprechenden Indizes from/ toder Suchunterbereiche können wie folgt generiert werden (von der gesamten Länge lotterybis 2):

int[] numbers = {23, 56, 67, 06, 43, 22, 59, 24, 90, 66};
int[] lottery = {01, 06, 43, 22, 89};

for (int n = lottery.length; n > 1; n--) {
    for (int m = 0; m <= lottery.length - n; m++) {
        int ix = indexOf(lottery, m, m + n, numbers);
        if (ix > -1) {
            System.out.printf("Found subarray %s, width=%d from: %d to %d ",
                    Arrays.toString(Arrays.copyOfRange(lottery, m, m + n)), n, m, m + n - 1);
            System.out.printf("at index: %d%n", ix);
        }
    }
}

Ausgabe

Found subarray [6, 43, 22], width=3 from: 1 to 3 at index: 3
Found subarray [6, 43], width=2 from: 1 to 2 at index: 3
Found subarray [43, 22], width=2 from: 2 to 3 at index: 4

Eine effizientere Implementierung würde den Knuth-Morris-Pratt-Algorithmus verwenden , um wiederkehrende Überprüfungen derselben Werte im Eingabearray zu umgehen.