1539. Kth Missing Positive Number

二分 O(logn) time O(1) space
找『上界』
跟1060. Missing Element in Sorted Array思路接近

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int n = size(arr), l = 0, r = n;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (arr[m] - m - 1 >= k) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l + k; // 上界之内已有的正数个数+消失的第k
    }
};

O(n) time O(1) space

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        arr.push_back(10000); // padding好写code
        for (int i = 0; i < arr.size(); ++i) {
            if (int d = arr[i] - (i + 1); d >= k) { // arr[i]出现在了第i + 1个位置，arr[i]前边本应该有arr[i] - 1个数，结果现在只有i个数，差了d个数，假如d >= k，说明差的第k个数必在这d个数里，因为是第一次出现这种情况，说明一定是从第arr[i]开始往前数第d - k + 1个数
                return arr[i] - (d - k + 1);
            }
        }
        return -1;
    }
};

不padding

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int n = arr.size();
        for (int i = 0; i < n; ++i) {
            if (int d = arr[i] - (i + 1); d >= k) {
                return arr[i] - (d - k + 1);
            }
        }
        return n + k; // 说明就是第n + k个数
    }
};