Kth 누락 양수 Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 Facebook Microsoft
알고리즘 배열 코딩 해싱 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 30

문제 설명

“Kth Missing Positive Number”문제에서 우리는 배열 arr이 주어집니다. 엄격히 증가 주문과 숫자 k.

우리의 임무는 배열에서 K 번째 양의 결측 수를 찾는 것입니다.

arr = [1,2,3,4], k = 2
6

설명 :

Kth 누락 양수 Leetcode 솔루션

주어진 배열에서와 같이 첫 번째 누락 된 숫자는 5이고 두 번째 누락 된 숫자는 6입니다. 따라서 답은 6입니다.

브루트 포스 AKth 누락 양수 Leetcode 솔루션에 대한 접근 방식

이 문제를 해결하기위한 무차별 대입 접근 방식은 다음과 같습니다.

  1. 배열을 횡단합니다.
  2. 매번 우리는 누락 된 숫자의 수를 계산할 것입니다.
  3. 누락 된 양수의 수가 k보다 크거나 같으면 i + k를 반환합니다.
  4. 누락 된 요소의 수가 k 미만이면 배열의 완전한 순회 후 배열의 크기 + k를 반환합니다.

실시

Kth 누락 양수에 대한 C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 
    int findKthPositive(vector<int>& arr, int k) {
        for(int i=0;i<arr.size();i++)
        {
            int x=arr[i]-(i+1);
            if(x>=k)
                return i+k;
        }
        return arr.size()+k;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4};
 int k=2;
 int ans=findKthPositive(arr,k);
 cout<<ans<<endl;
 return 0;
}
6

Kth 누락 양수에 대한 Java 코드

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static int findKthPositive(int[] arr, int k) {
        for(int i=0;i<arr.length;i++)
        {
            int x=arr[i]-(i+1);
            if(x>=k)
                return i+k;
        }
        return arr.length+k;
    }   
  public static void main(String[] args) {
        int [] arr = {1,2,3,4};
        int k=2;
        int ans=findKthPositive(arr,k); 
        System.out.println(ans);
  }
}
6

K 번째 결측 양수 Leetcode 솔루션의 복잡성 분석

시간 복잡성

위 코드의 시간 복잡성은 O (N) 최악의 경우 O (n) 시간이 걸리는 선형 검색을 사용하기 때문입니다. 여기서 n은 주어진 배열의 길이입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (1) 답을 저장하는 데 변수 만 사용하고 있기 때문입니다.

이진 검색 AKth 누락 양수 Leetcode 솔루션에 대한 접근 방식

위의 알고리즘의 시간 복잡도는 최악의 경우 전체 배열을 탐색해야 할 수 있기 때문에 O (n)입니다. 선형 검색 대신 이진 검색을 사용하여 솔루션의 시간 복잡성을 개선 할 수 있습니다.

  1. 먼저 이진 검색에 대한 검색 범위를 정의하겠습니다. 따라서 start는 인덱스 0이되고 end는 주어진 배열의 마지막 인덱스가됩니다.
  2. 중간 인덱스를 찾은 다음 누락 된 양수의 수가 k 미만인지 확인합니다.
    1. 시작은 mid + 1이됩니다.
    2. 그렇지 않으면 끝이 중간이됩니다.
  3. end + k를 반환합니다.

실시

Kth 누락 양수에 대한 C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 
int findKthPositive(vector<int>& A, int k) {
        int l = 0, r = A.size(), m;
        while (l < r) {
            m = (l + r) / 2;
            if (A[m] - 1 - m < k)
                l = m + 1;
            else
                r = m;
        }
        return l + k;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4};
 int k=2;
 int ans=findKthPositive(arr,k);
 cout<<ans<<endl;
 return 0;
}
6

Kth 누락 양수에 대한 Java 코드

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static int findKthPositive(int[] A, int k) {
        int l = 0, r = A.length, m;
        while (l < r) {
            m = (l + r) / 2;
            if (A[m] - 1 - m < k)
                l = m + 1;
            else
                r = m;
        }
        return l + k;
    }  
  public static void main(String[] args) {
        int [] arr = {1,2,3,4};
        int k=2;
        int ans=findKthPositive(arr,k); 
        System.out.println(ans);
  }
}
6

K 번째 결측 양수 Leetcode 솔루션의 복잡성 분석

시간 복잡성

위 코드의 시간 복잡성은 O (로그 n) 최악의 경우 O (logn) 시간이 걸리는 이진 검색을 사용하기 때문입니다. 여기서 n은 주어진 배열의 길이입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (1) 답을 저장하는 데 변수 만 사용하고 있기 때문입니다.

참조

코멘트를 남겨

Translate »