[LeetCode] 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个缺失的正整数。

题意是给一个升序的数组和一个数字K，请返回第K个缺失的正整数。这道题和1060题是一模一样，但是这道题是easy的原因在于数据范围很小，nums[i] 只到1000。

这道题有好几种解法，我这里都列出来。分别是暴力解，线性解和二分法。

首先是暴力解，用一个指针扫描input数组，去看每一个位置上的数字是否是要找的数字target。一开始target = 1，意思是从1开始找，如果能在input数组中找到每个正整数，则接着往后遍历；但凡有一个正整数找不到，就把这个缺失的正整数加到一个list中，直到这个list的size达到K。但是也有可能list没有到K，input数组就遍历完了，此时可以把缺失的整数用一个while循环模拟完。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public int findKthPositive(int[] arr, int k) {
 3         int target = 1;
 4         int i = 0;
 5         List<Integer> missingOnes = new ArrayList<>();
 6         while (i < arr.length) {
 7             // if the target number is found
 8             if (arr[i] == target) {
 9                 i++;
10                 target++;
11             }
12             // if it's not found
13             else {
14                 missingOnes.add(target);
15                 target++;
16             }
17         }
18         int size = missingOnes.size();
19         int count = size;
20         int lastNumber = (missingOnes.size() == 0) ? arr[arr.length - 1]
21                 : Math.max(arr[arr.length - 1], missingOnes.get(missingOnes.size() - 1));
22         if (count >= k) {
23             return missingOnes.get(k - 1);
24         } else {
25             while (count < k) {
26                 lastNumber++;
27                 count++;
28             }
29             return lastNumber;
30         }
31     }
32 }

一个比较优化的线性解法是，因为题目给的是一个升序的正整数数组，而且数组理论上是从1开始。所以理想情况下，数字nums[i]和它对应的下标i的关系应该是nums[i] = i + 1。所以在扫描input数组的时候，如果发觉数字和他对应的下标的差大于1了，则说明中间开始缺失数字了。当这个差距大于等于K的时候，则找到了第K个缺失的数字。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int findKthPositive(int[] arr, int k) {
 3         int len = arr.length;
 4         for (int i = 0; i < len; i++) {
 5             if (arr[i] - i - 1 >= k) {
 6                 return k + i;
 7             }
 8         }
 9         return k + len;
10     }
11 }

二分法。因为input数组是有序的，所以如果面试官不满意O(n)级别的思路的话，可以试图往二分法上靠。mid找到中点，还是跟第二种做法类似，比较当前这个index上的数字和index的差值。如果差值小于K，则往数组的右半边找；反之则往数组的左半边找。

时间O(logn)

空间O(1)

Java实现一，right 指针一开始在数组范围外

 1 class Solution {
 2     public int findKthPositive(int[] arr, int k) {
 3         int left = 0;
 4         int right = arr.length;
 5         int mid = 0;
 6         while (left < right) {
 7             mid = left + (right - left) / 2;
 8             if (arr[mid] - mid >= k + 1) {
 9                 right = mid;
10             } else {
11                 left = mid + 1;
12             }
13         }
14         return left + k;
15     }
16 }

Java实现二，right 指针一开始在数组范围内。因为 right = nums.length - 1，mid 指针能碰到的范围是在 [left, right] 之间，所以当 mid 不满足判断条件的时候，left = mid + 1，right = mid - 1。

 1 class Solution {
 2     public int findKthPositive(int[] arr, int k) {
 3         int left = 0;
 4         int right = arr.length - 1;
 5         while (left <= right) {
 6             int mid = left + (right - left) / 2;
 7             int missing = arr[mid] - mid - 1;
 8             if (missing < k) {
 9                 left = mid + 1;
10             } else {
11                 right = mid - 1;
12             }
13         }
14         return left + k;
15     }
16 }

JavaScript实现一

 1 /**
 2  * @param {number[]} arr
 3  * @param {number} k
 4  * @return {number}
 5  */
 6 var findKthPositive = function (arr, k) {
 7     let start = 0;
 8     let end = arr.length - 1;
 9     while (start <= end) {
10         let mid = start + Math.floor((end - start) / 2);
11         let missing = arr[mid] - mid - 1;
12         if (missing < k) {
13             start = mid + 1;
14         } else {
15             end = mid - 1;
16         }
17     }
18     return start + k;
19 };

JavaScript实现二

 1 /**
 2  * @param {number[]} arr
 3  * @param {number} k
 4  * @return {number}
 5  */
 6 var findKthPositive = function (arr, k) {
 7     let start = 0;
 8     let end = arr.length;
 9     while (start < end) {
10         let mid = start + Math.floor((end - start) / 2);
11         let missing = arr[mid] - mid - 1;
12         if (missing < k) {
13             start = mid + 1;
14         } else {
15             end = mid;
16         }
17     }
18     return start + k;
19 };