1539. 第 k 个缺失的正整数

墨蓝 2022-09-05 01:57 160阅读 0赞

[https://leetcode-cn.com/problems/kth-missing-positive-number/][https_leetcode-cn.com_problems_kth-missing-positive-number]

给你一个 **严格升序排列** 的正整数数组 `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]`

class Solution {
        public int findKthPositive(int[] arr, int k) {
            if(arr[0]!=1)
            {
                if((arr[0]-1)>=k)
                {
                    return k;
                }
                else k-=(arr[0]-1);
            } 
            int t = 0;
            for(int i=0;i<arr.length-1;i++)
            {
                t = arr[i+1]-arr[i];
                System.out.println(t);
                if(t!=1)
                { 
                    if(k>(t-1))  k = k-(t-1);
                    else return arr[i]+k;
                }
            }
            if(k!=0)return arr[arr.length-1]+k;
            return k;
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dldHVnbHk_size_16_color_FFFFFF_t_70][]

[https_leetcode-cn.com_problems_kth-missing-positive-number]: https://leetcode-cn.com/problems/kth-missing-positive-number/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dldHVnbHk_size_16_color_FFFFFF_t_70]: /images/20220829/1ca6fd3cbff74a57b67fbeea53a72173.png