1539. Kth Missing Positive Number

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the kth positive integer that is missing from this array.

 

Example 1:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.
Example 2:

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.
 

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length

这题让我们求出第k个缺失的数字。完整的数字序列是从1开始的连续数字。

一开始用set硬破，时间复杂度和空间复杂度感人，自己都看不下去了，又换了个想法来写。

首先我们遍历数组，求出当前缺失的数字个数，假设k减去这个个数后不为0,则还有缺失的数字，则减去该次缺失的数字之后向下扫描。反之直接用当前的数字加上缺失的个数即可得到结果。

class KthMissingPositiveNumber : public Solution {
public:
    void Exec() {

    }
    int findKthPositive(vector<int>& arr, int k) {
        unordered_set<int> arrset;
        for (auto v : arr) {
            arrset.insert(v);
        }
        int missing = 0;
        for (int i = 1; ; i++) {
            if (arrset.count(i) == 0) {
                arrset.insert(i);
                missing++;
                if (missing == k) {
                    return i;
                }
            }
        }
        return 0;
    }
    int findKthPositive1(vector<int>& arr, int k) {
        int missing = 0, base = 0;
        for (auto v : arr) {
            int curMissing = v - base - 1;
            if (curMissing >= k) {
                return base + k;
            }
            k -= curMissing;
            base = v;
        }
        return base + k;
    }
};