Kth 누락 양수 Leetcode 솔루션-TutorialCup

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

Twitter Facebook 링크드인 버퍼 레딧 텀블러

차례

문제 설명

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

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

예

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

설명 :

핀

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

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

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

배열을 횡단합니다.
매번 우리는 누락 된 숫자의 수를 계산할 것입니다.
누락 된 양수의 수가 k보다 크거나 같으면 i + k를 반환합니다.
누락 된 요소의 수가 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;
}

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

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

시간 복잡성

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

공간 복잡성

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

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

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

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

실시