첫 번째 누락 긍정


난이도 하드
자주 묻는 질문 Accolite 아마존 팩트 셋 삼성 스냅 딜
배열

문제 정책

"첫 번째 양수 누락"문제는 n 크기의 배열 a [] (정렬 또는 정렬되지 않음)가 제공된다는 것을 나타냅니다. 이 배열에서 누락 된 첫 번째 양수를 찾습니다.

첫 번째 누락 긍정

a[ ] = {1, 3, -1, 8}
 2

설명 : 배열을 정렬하면 {-1, 1, 3, 8}을 얻습니다. 우리는 부정적인 것을 다루지 않습니다 정수 그래서 우리가 -1/0인지 아닌지는 중요하지 않습니다. 그러나 그 후 배열에 1의 숫자가 있는지 여부가 우려됩니다. 따라서 1이 있고 다음 숫자는 3입니다. 그러나 2는 없습니다. 이것이 배열에없는 첫 번째 양의 정수가됩니다.

a[ ] = {9, -1, 8, 7}
1

설명 : 다시 한 번 종류 배열을 확인한 다음 1부터 시작하는 양의 정수가 있는지 확인합니다. 정렬 후 {-1, 7,8,9}가 있습니다. 따라서 우리는 배열에 존재하지 않는 첫 번째 양의 정수가 1임을 압니다.

접근

정렬 사용

첫 번째 누락 된 양성을 찾는 알고리즘

1. Initialize a non-empty array a[ ] of size n.
2. Initialize an integer variable min as 1 to store the smallest positive missing element.
3. Sort the given array a[ ] of size n.
4. Traverse through the array a[ ] and check if the element at the current index in array a[ ] is equal to the variable min, increment the variable min by 1.
5. Return the variable min.

따라서 위에서 설명한 입력 / 출력 섹션에서 먼저 입력을 정렬 한 다음 배열에없는 첫 번째 양의 정수를 확인했습니다. 하지만 정렬을 사용했기 때문에이 방법은 충분히 효율적이지 않습니다.

암호

첫 번째 누락 된 긍정을 찾는 C ++ 프로그램
#include <bits/stdc++.h> 
using namespace std; 

int missPositive(int a[], int n){ 
    int min=1;
    sort(a, a+n);
    for(int i=0; i<n; i++){
        if(a[i]==min){
            min++;
        }
    }
    return min;
}  
int main(){ 
    int a[] = {9, -1, 1, 8, 7}; 
    int n = sizeof(a)/sizeof(a[0]);
    cout<<missPositive(a, n); 
    return 0; 
} 
2
첫 번째 누락 긍정을 찾는 자바 프로그램
import java.util.Arrays;
class missing{
    static int missPositive(int a[], int n){ 
        int min=1;
        Arrays.sort(a);
        for(int i=0; i<n; i++){
            if(a[i]==min){
                min++;
            }
        }
        return min;
    }
  public static void main (String[] args){
        int a[] = {9, -1, 1, 8, 7};
        int n = a.length;
        System.out.println(missPositive(a, n));
  }
}

2

복잡성 분석

시간 복잡성

O (N log N) 여기서 n은 주어진 배열 a []에있는 요소의 수입니다.

공간 복잡성

의 위에) n 개의 요소를 저장하기 위해 공간을 사용했기 때문입니다.

효율적인 방법

첫 번째 결측 긍정을 효율적으로 찾는 알고리즘

1. Initialize a non-empty array a[ ] of size n.
2. Initialize two variables of integer type val and nextval to store the current element and the next element of the array respectively.
3. Traverse through the array a[ ] and check if the element at current index in array a[ ] is greater than 0 or the element at current index in array a[ ] is greater than the array size store it in val. Traverse the array until we reach an element that is already marked or could not be marked.
4. Again Traverse the array and find the first array index which is not marked and is the smallest missing number. Return index + 1.
5. Else if all the index are marked return n +1.

그래서 순진한 접근 방식으로 배열을 정렬했습니다. 그리고 답을 찾았습니다. 여기서 우리는 배열을 표시하는 대신 배열을 정렬하지 않을 것입니다. 마킹함으로써 우리는 요소의 값과 같은 인덱스에 요소를 배치 할 것입니다. 이렇게하면 어떤 숫자가 첫 번째 누락 된 양성인지 확인할 수 있습니다.

암호

첫 번째 누락 된 긍정을 찾는 C ++ 프로그램
#include <bits/stdc++.h> 
using namespace std; 

int missPositive(int a[], int n){ 
    int num, nextnum; 
    for(int i=0; i<n; i++){ 
        if ((a[i]<=0) || (a[i]>n))
            continue; 
  
        num = a[i]; 
  
        while(a[num - 1] != num) { 
            nextnum = a[num - 1]; 
            a[num - 1] = num; 
            num = nextnum; 
            if ((num<=0) || (num>n)) 
                break; 
        } 
    } 
    for(int i=0; i<n; i++) { 
        if (a[i] != i+1) { 
            return i+1; 
        } 
    } 
    return n + 1; 
}  
int main(){ 
    int a[] = {9, -1, 1, 8, 7}; 
    int n = sizeof(a)/sizeof(a[0]);
    cout<<missPositive(a, n); 
    return 0; 
}
2
첫 번째 누락 긍정을 찾는 자바 프로그램
class missing{
    static int missPositive(int a[], int n){ 
        int num, nextnum; 
      
        for(int i=0; i<n; i++){ 
            if (a[i] <= 0 || a[i] > n) 
                continue; 
      
            num = a[i]; 
      
            while(a[num - 1] != num) { 
                nextnum = a[num - 1]; 
                a[num - 1] = num; 
                num = nextnum; 
                if (num <= 0 || num > n) 
                    break; 
            } 
        } 
      
        for(int i=0; i<n; i++) { 
            if (a[i] != i+1) { 
                return i+1; 
            } 
        } 
        return n + 1; 
    }  
  public static void main (String[] args){
    int a[] = {9, -1, 1, 8, 7}; 
    int n = a.length;
    System.out.println(missPositive(a, n));
  }
}
2

복잡성 분석

시간 복잡성

의 위에) 여기서 n은 주어진 배열 a []에있는 요소의 수입니다.

공간 복잡성

O (1) 일정한 추가 공간을 사용했기 때문입니다.