Java, um herauszufinden, ob ein Array eine Teilmenge eines anderen ist
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
Es scheint, dass eine ähnliche Methode String::indexOf
in 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 search
Subarrays ( lottery
) gesucht werden . Daher sollte die erwähnte Methode erweitert werden, um nach einem Unterbereich des search
Arguments 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
/ to
der Suchunterbereiche können wie folgt generiert werden (von der gesamten Länge lottery
bis 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.