Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.
Return 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.
比较简单的做法是： 我们比较两个连续的两个数，如果他们之间相差大于1，我们需要decrease k 直到k变成0. 我们需要考虑两边的情况。
1 class Solution { 2 public int findKthPositive(int[] arr, int k) { 3 if (arr == null || arr.length == 0) return -1; 4 if (arr[0] != 1) { 5 if (arr[0] - 1 >= k) return k; 6 k = k - (arr[0] - 1); // arr[0] -1 refers to the missing numbers before arr[0] 7 } 8 9 for (int i = 1; i < arr.length; i++) { 10 int diff = arr[i] - arr[i - 1] - 1; 11 if (diff >= k) { 12 return arr[i - 1] + k; 13 } else { 14 k -= diff; 15 } 16 17 } 18 return arr[arr.length - 1] + k; 19 }
O(lgn)的解法：
https://leetcode.com/problems/kth-missing-positive-number/solutions/779999/java-c-python-o-logn/
My two cents on thought process for binary search:
Here we have three sorted sequences:
let n be len(A), then
1st sorted sequence is array values:
2nd is indices:
The nice part about this question: the indices can help us to get all the positive numbers in sorted order (i + 1 if i denotes the index)
Hence, A[i] - (i + 1) will be # of missing positives at index i, and this will be our 3rd sorted sequences
i.e.
A: [1,3,4,6]
A[i] - (i+1): [0,1,1,2]let's call array A[i]-(i+1) as B, which is [0, 1, 1, 2] above, then B[i] represents how many missing positives so far at index i.
So the question becomes: finding the largest index of array B so that B[j] is smaller than K.
It is the same as finding first/last occurrence 34. find-first-and-last-position-of-element-in-sorted-array
l, r = 0, len(B)
while l <= r:
m = (r + l) / 2
if B[m] < K:
l = m + 1
else:
r = m - 1After while loop is stopped, l - 1 is our target index because, B[l - 1] represents how many positive is missing at index l - 1 that is smaller than K, so result is A[l -1](the largest number in A that is less than result) + K - B[l - 1](offset, how far from result) = (A[l - 1]) + (k - (A[l - 1] - l)) = l + k
1 public int findKthPositive(int[] A, int k) { 2 int l = 0, r = A.length - 1, m; 3 while (l <= r) { 4 m = (l + r) / 2; 5 if (A[m] - (1 + m) < k) 6 l = m + 1; 7 else 8 r = m - 1; 9 } 10 return l + k; 11 }
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。