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 <= 10001 <= arr[i] <= 10001 <= k <= 1000arr[i] < arr[j]for1 <= i < j <= arr.length
Solution 1: HashTable
Store all the elements into a hashtable, and check from 1 to max(arr).
Time complexity: O(max(arr)) ~ O(1000)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: int findKthPositive(vector<int>& arr, int k) { unordered_set<int> s(begin(arr), end(arr)); for (int i = 1; i <= arr.back(); ++i) { if (!s.count(i)) --k; if (k == 0) return i; } return arr.back() + k; } }; |
Solution 2: Binary Search
We can find the smallest index l using binary search, s.t.
arr[l] – l + 1 >= k
which means we missed at least k numbers at index l.
And the answer will be l + k.
Time complexity: O(logn)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: int findKthPositive(vector<int>& arr, int k) { int l = 0; int r = arr.size(); while (l < r) { int m = l + (r - l) / 2; if (arr[m] - (m + 1) >= k) r = m; else l = m + 1; } return l + k; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution { public int findKthPositive(int[] arr, int k) { int l = 0; int r = arr.length; while (l < r) { int m = l + (r - l) / 2; if (arr[m] - (m + 1) >= k) r = m; else l = m + 1; } return l + k; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 |
class Solution: def findKthPositive(self, arr: List[int], k: int) -> int: l, r = 0, len(arr) while l < r: m = l + (r - l) // 2 if arr[m] - (m + 1) >= k: r = m else: l = m + 1 return l + k |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment