# 1539. Kth Missing Positive Number
###### tags: `Leetcode` `Medium` `FaceBook` `Binary Search`
Link: https://leetcode.com/problems/kth-missing-positive-number/
## 思路
### 思路一
看到sorted array就想到binary search
每个数字前边缺少的数字就是arr[i]-i-1
### 思路二
一定要想好再写...
考虑完各种情况再写...
枚举每一个可能出现的数字
## Code
### 思路一 O(logN)

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int start = 0;
        int end = arr.length;
        int mid = (start+end)/2;
        while(start<end){
            mid = (start+end)/2;
            if(arr[mid]-mid-1<k){
                start = mid+1;
            }
            else{
                end = mid;
            }
        }
        // return arr[start-1]+k-(arr[start-1]-(start-1)-1);
        return start+k;
    }
}

### 思路二 O(N)

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int idx = 0;
        int cnt = 0;
        for(int i = 1;i < arr[arr.length-1];i++){
            if(i < arr[idx]){
                cnt++;
            }
            else{
                idx++;
            }
            if(cnt == k){
                return i;
            }
        }
        return arr[arr.length-1]+k-cnt;
    }
}