原文链接: https://leetcode-cn.com/problems/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

中文题目

给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。

请你找到这个数组里第 k 个缺失的正整数。

 

示例 1：

输入：arr = [2,3,4,7,11], k = 5
输出：9
解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。

示例 2：

输入：arr = [1,2,3,4], k = 2
输出：6
解释：缺失的正整数包括 [5,6,7,...] 。第 2 个缺失的正整数为 6 。

 

提示：

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 1000
• 1 <= k <= 1000
• 对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j] 

通过代码

高赞题解

• 解法1：暴力解法

首先最容易想到的莫过于暴力解法，由于1 <= arr[i] <= 1000,1 <= k <= 1000,因而返回的答案不超过2000，不妨把数组开大一些，然后扫描arr，将所有这些出现的元素标记为-1,最后查找第K个不等于-1的元素即可。

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int i,ret = 0;
        int[] ans = new int[2010];
        for( i = 1;i <= 2000; i++) ans[i] = i; 
        for( i = 0;i < arr.length;i++){
            ans[arr[i]] = -1;
        }
        for(i = 1;i <= 2000; i++){
            if(ans[i]==-1){
                continue;   
            }else{
                k--;
                if(k==0)break;
            }
        }
        return ans[i];
    }
}

• 解法2：利用arr[i]与其下标i关系

不难发现，一个不缺失元素的序列，会有arr[i]=i+1这样的关系，而在缺失元素之后，会有arr[i]>i+1，简单移项可得 arr[i]-i-1 > 0，缺失一个的时候，相差1，两个则相差2，以此类推，缺失越多，两者差距越大，我们要找第k个缺失的，换言之，只要arr[i]-i-1 == k,我们便找到了题目要找的数字。

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int i,n = arr.size();
        for(i=0;i<n;i++){
            if(arr[i]-i-1>=k){
                return k+i;
            }
        }
        return k+i;//亦可写成：k+n，只不过写成k+i方便理解下面一个解法
    }
};

• 解法3：二分查找

然而上述的解法没有用上题目给出的条件 严格升序排列，已经找出了 arr[i]-i-1 > 0关系之后，我们可以利用上述的线性查找的方式改为二分查找的方式。

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int left = 0, right = arr.size(), mid = 0;
        while(left<right){
            mid = left + (right-left)/2;
            if(arr[mid]-mid >= k+1){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return k + left;
    }
};

统计信息

通过次数	提交次数	AC比率
17557	32524	54.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言