配列が別の配列のサブセットであるかどうかを確認するJava
Nov 24 2020
特定の量の数値が別の配列にあるかどうかを確認するのに問題があります。最初の配列は10個の乱数を生成し、2番目の配列ではユーザーが5個の数値を推測します。ユーザーがシーケンスを推測したかどうかを確認しようとしています。ユーザー入力の数が10の配列の1〜5のいずれかの数であるかどうかを確認するためにループし、そうでない場合は2〜6の数をチェックします。たとえば、プログラムの当選番号が23 56 67 06 43 22 59 24 90 66で、ユーザーが入力した場合:01 06 432289。インデックスが範囲外になり続けます。これを修正するにはどうすればよいですか?
// 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;
}
}
}
回答
1 AlexRudenko Nov 24 2020 at 20:50
String::indexOf
サブ配列のインデックスを見つけようとする配列に対して、このタスクで同様の方法を実装する必要があるようint indexOf(int[] search, int[] input)
です。
また、それを探すために必要となる可能性があるすべての可能なサブアレイのsearch
部分配列(lottery
)。したがって、前述のメソッドを拡張して、search
引数のサブ範囲を探す必要があります。int indexOf(int[] search, int[] input)
簡単な実装は次のようになります。
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;
}
検索サブ範囲の幅と適切なインデックスfrom
/to
は、次のように生成できます(全長lottery
から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);
}
}
}
出力
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
より効率的な実装では、Knuth-Morris-Prattアルゴリズムを使用して、入力配列内の同じ値の繰り返しチェックをバイパスします。