algo-aha

[1..n]间的数，有的出现2次、有的1次、有的缺失，找缺失的那些数（in-place算法）

• https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array

vector<int> findDisappearedNumbers(vector<int>& nums){
    // 把数x当作下标（1-based），将nums[x-1]标记为负数
    for (int num : nums) {
        int x = abs(num);
        if (nums[x-1] > 0) nums[x-1] *= -1;
    }
    vector<int> ans;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] > 0) ans.push_back(i+1);
    }
    return ans;
}

第一个缺失的正整数（数组有负数）

• https://leetcode.com/problems/first-missing-positive/

比如[1,2,0]返回3，[3,4,-1,1]返回2

int firstMissingPositive(vector<int>& nums) {
    // 期望变成数组[1..n]。位置i应放数i+1，即nums[i]==i+1
    // => nums[i]-1==i，nums[nums[i]-1]==nums[i]
    // 旋转置换：若nums[nums[i]-1]!=nums[i]，交换这两处的值
    const int N = nums.size();
    for (int i = 0; i < N; i++) {
        while (1 <= nums[i] && nums[i] <= N && nums[nums[i]-1] != nums[i]) {
            swap(nums[nums[i]-1], nums[i]);
        }
    }
    // first missing
    for (int i = 0; i < N; i++) {
        if (nums[i] != i + 1) return i + 1;
    }
    return N + 1;
}

第k个缺失的正整数（有序正数组）

• https://leetcode.com/problems/kth-missing-positive-number

int findKthPositive(vector<int>& arr, int k) {
    // 题目：找第k小的缺失自然数
    // 假设arr[i]全部>k，所求就是k；从左往右遇到arr[i]<=k，就递增k
    for (int num : arr) { // arr[]是递增数组
        if (num <= k) k++;
        else break;
    }
    return k;
}    

也可用二分搜索解决

int findKthPositive(vector<int>& arr, int k) {
    // 题目：找第k小的缺失自然数
    // 数组arr和缺失数组mis可拼成自然数序列，
    // 值arr[m]是自然数序列的第arr[m]个元素，又是数组arr的第m+1个元素，
    // 所以<=arr[m]的缺失数count(m)=arr[m]-(m+1)
    // 因为arr[m]比m增加得快，count(m)是关于m的递增函数，
    // 条件式enough(m){count(m)>=k}满足二分搜索的条件形式[0..0 1..1]
    int l = -1, u = arr.size();
    while (l + 1 < u) {
        int m = l + (u - l) / 2;
        if (enough(m, arr, k)) {
            u = m;
        } else {
            l = m;
        }
    }
    // <=arr[u]的缺失数首次有>=k个。
    // <=arr[u-1]的缺失数有count(u-1)=arr[u-1]-u个，
    // 比起需要的k个，还差k-(arr[u-1]-u)个，
    // 第k个缺失数为 arr[u-1]+(k-(arr[u-1]-u)) = u+k
    return u + k;
}

bool enough(int m, vector<int>& arr, int k) {
    return arr[m] - (m + 1) >= k;
}

给数组补一些数，使[1..n]的数都能由数组数相加获得

• https://leetcode.com/problems/patching-array/

贪心法

int minPatches(vector<int>& nums, int n) {
    // 设[1..missing)已能由数组数相加获得，尝试扩展上边界missing
    long missing = 1;
    int i = 0, ans = 0;
    while (missing <= n) { // 最终missing>n，[1..missing)包含[1..n]
        // nums[i]已能由相加获得（<missing）或在数组中（=missing）
        if (i < nums.size() && nums[i] <= missing) {
            missing += nums[i];
            i++;
        } else {
            missing += missing; // 补上数missing
            ans++;
        }
    }
    return ans;
}