배열이 다른 배열의 하위 집합인지 찾기위한 Java

Nov 24 2020

특정 양의 숫자가 다른 배열에 있는지 확인하는 데 문제가 있습니다. 첫 번째 배열은 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;
            }
        }
    }

답변

1 AlexRudenko Nov 24 2020 at 20:50

String::indexOf하위 배열의 인덱스를 찾으려고하는 배열에 대해이 작업에서 이와 유사한 방법을 구현해야하는 것 같습니다 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 알고리즘 을 사용하여 입력 배열의 동일한 값에 대한 반복적 인 검사를 우회합니다.