class Solution {
public:
int findKthPositive(vector<int> &arr, int k) {
int left = 0, right = arr.size() - 1, missing;
// Use binary search to find the smallest index, i, such that
// arr[i] - i - 1 is greater than or equal k.
// That is, k <= arr[i] - i - 1 is true.
while (left < right) {
int middle = left + (right - left) / 2;
missing = arr[middle] - middle - 1;
if (missing < k) {
left = middle + 1;
} else {
right = middle;
}
}
missing = arr[left] - left - 1;
if (missing < k) {
// The k-th missing integer shows up afer arr[left].
// arr[left] + (k - missing)
// => arr[left] + (k - arr[left] + left + 1)
// => arr[left] + k - arr[left] + left + 1
// => left + k + 1
return left + k + 1;
}
// The k-th missing integer shows up before arr[left].
// arr[left] - (missing - k + 1)
// => arr[left] - (arr[left] - left - 1 - k + 1)
// => arr[left] - arr[left] + left + k
// => left + k
return left + k;
}
};
arr
.
My Solution Solution 1: DFS (recursion) The Key Idea for Solving This Coding Question C++ Code /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right;
Jun 6, 2025MyCircularQueueO(k)
Apr 20, 2025O(m)
Mar 4, 2025O(n)n is the length of nums.
Feb 19, 2025or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up