Computer >> 컴퓨터 >  >> 프로그램 작성 >> Java

정렬되지 않은 정수 배열에서 누락된 양수를 찾는 프로그램을 Java로 작성하십시오.

<시간/>

정렬되지 않은 정수 배열을 제공했다고 가정해 보겠습니다. 작업은 [0 ~ n] 범위의 지정된 배열에 없는 양의 누락된 숫자를 찾는 것입니다. 예를 들어,

입력-1 -

N = 9
arr = [0,2,5,9,1,7,4,3,6]

출력 -

8

설명 − 주어진 정렬되지 않은 배열에서 '8'이 누락된 유일한 양의 정수이므로 출력은 '8'입니다.

입력-2 -

N = 1
arr = [0]

출력 -

1

설명 − 주어진 배열에서 '1'이 누락된 유일한 양의 정수이므로 출력은 '1'입니다.

이 문제를 해결하기 위한 접근 방식

이 특정 문제를 해결하기 위한 몇 가지 접근 방식이 있습니다. 그러나 선형 시간 O(n) 및 일정 공간 O(1)에서 이 문제를 해결할 수 있습니다.

배열의 크기가 n이고 정확히 [0에서 n] 범위의 요소를 포함한다는 것을 알고 있기 때문입니다. 따라서 각 요소와 해당 인덱스에 대해 'n'으로 XOR 연산을 수행하면 결과 숫자를 배열에서 누락된 고유 숫자로 찾을 수 있습니다.

  • [0 ~ n] 범위의 요소가 있는 N 크기의 배열을 입력합니다.

  • 정수 함수 findMissingNumber(int arr[], int size)는 배열과 그 크기를 입력으로 받아 누락된 숫자를 반환합니다.

  • n XOR 연산을 수행하기 위해 누락된 숫자로.

  • 모든 배열 요소에 대해 반복하고 누락된 숫자, 즉 n과 관련하여 각 배열 요소 및 해당 인덱스에 대해 XOR 연산을 수행합니다.

  • 이제 누락된 번호를 반환하십시오.

public class Solution {
   public static int findMissingNumber(int arr[], int size){
      int missing_no= size;
      for(int i=0;i<size;i++){
         missing_no^= i^arr[i];
      }
      return missing_no;
   }
   public static void main(String[] args){
      int arr[] = {0,4,2,1,6,3};
      int n = arr.length;
      int a=findMissingNumber(arr, n);
      System.out.println(a);
   }
}

출력

위의 코드를 실행하면 다음과 같이 출력이 생성됩니다.

5

주어진 배열 {0,4,2,1,6,3}에서 '5'가 누락되었으므로 5를 반환합니다.