时间戳

首页 > 解决方案 > Java判断一个数组是否是另一个数组的子集

java - Java判断一个数组是否是另一个数组的子集

问题描述

我很难找出特定数量的数字是否在另一个数组中。第一个数组生成 10 个随机数，在第二个数组中用户猜测 5 个数字。我试图找出用户是否猜到了任何序列。我用于循环找出用户输入的数量是否在 10 的数组中从 1-5 的任何数字中，如果不是，它将检查数字 2-6 等等。例如，如果程序有以下中奖号码：23 56 67 06 43 22 59 24 90 66 并且用户输入：01 06 43 22 89。我总是让索引超出范围。我该如何解决这个问题？

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

标签： java

解决方案

String::indexOf对于试图查找 subarray 索引的数组，似乎应该在此任务中实施类似于的方法int indexOf(int[] search, int[] input)。

此外，可能需要查找子数组 ( )的所有可能子数组。因此，应该扩展上述方法以查找参数的子范围：searchlotterysearchint 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 算法来绕过对输入数组中相同值的重复检查。

推荐阅读