2023-05-16：给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。
请你找到这个数组里第 k 个缺失的正整数。
输入：arr = [2,3,4,7,11], k = 5。
输出：9。
答案 2023-05-16：
大体步骤如下：
1.初始化左指针 l 为 0，右指针 r 为数组长度减一，定义中间指针 m 和 find（找到第 k 个正整数前的下标位置），并将 find 初始化为数组长度。
2.当左指针小于等于右指针时，执行二分查找。令 m 等于左指针和右指针之间的中间值。（注：这里取中间值可以使用位运算优化）。
3.如果当前位置 arr[m]减去（m+1）大于等于 k，说明第 k 个缺失的正整数在当前位置左侧，更新 find 为当前位置 m，并把右指针 r 设为 m-1，继续二分查找左半部分。
4.如果当前位置 arr[m]减去（m+1）小于 k，说明第 k 个缺失的正整数在当前位置右侧，把左指针 l 设为 m+1，继续二分查找右半部分。
5.查找结束后，如果 find 等于 0，说明要找的是第一个缺失的正整数，返回 0 即可；否则，找到第 k 个正整数前的一个位置，把这个位置上的元素赋值给 preValue，计算从当前位置到第 k 个正整数的缺失数量 under，最终结果就是 preValue 加上 k 减去 under 的值。
6.返回结果。
时间复杂度为 O(logn)，其中 n 是数组的长度。因为代码采用了二分查找的算法，每次查找可以将搜索范围缩小一半，所以时间复杂度为 O(logn)。
空间复杂度为 O(1)，因为代码只使用了常数个变量来存储中间结果，与输入数据的规模大小无关。因此，空间复杂度为常数级别。
go 完整代码如下：
package main
import "fmt"
func findKthPositive(arr []int, k int) int { l := 0 r := len(arr) - 1 m := 0 find := len(arr) for l <= r { m = (l + r) / 2 if arr[m]-(m+1) >= k { find = m r = m - 1 } else { l = m + 1 } } preValue := 0 if find == 0 { preValue = 0 } else { preValue = arr[find-1] } under := preValue - find return preValue + (k - under)}
func main() { arr := []int{2, 3, 4, 7, 11} k := 5 result := findKthPositive(arr, k) fmt.Println(result)}
复制代码
rust 完整代码如下：
fn find_kth_positive(arr: Vec<i32>, k: i32) -> i32 { let mut l = 0; let mut r = arr.len() - 1; let mut m = 0; let mut find = arr.len(); while l <= r { m = (l + r) / 2; if arr[m] - (m as i32 + 1) >= k { find = m; r = m - 1; } else { l = m + 1; } } let pre_value = if find == 0 { 0 } else { arr[find - 1] }; let under = pre_value - (find as i32); return pre_value + (k - under);}
fn main() { let arr: Vec<i32> = vec![2, 3, 4, 7, 11]; let k: i32 = 5; let result = find_kth_positive(arr, k); println!("{}", result);}
复制代码
c 语言完整代码如下：
#include <stdio.h>
int findKthPositive(int* arr, int arrSize, int k) { int l = 0; int r = arrSize - 1; int m = 0; int find = arrSize; while (l <= r) { m = (l + r) / 2; if (arr[m] - (m + 1) >= k) { find = m; r = m - 1; } else { l = m + 1; } } int preValue = find == 0 ? 0 : arr[find - 1]; int under = preValue - find; return preValue + (k - under);}
int main() { int arr[] = { 2, 3, 4, 7, 11 }; int k = 5; int arrSize = sizeof(arr) / sizeof(arr[0]); int result = findKthPositive(arr, arrSize, k); printf("%d\n", result);}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>
using namespace std;
int findKthPositive(vector<int>& arr, int k) { int l = 0; int r = arr.size() - 1; int m = 0; int find = arr.size(); while (l <= r) { m = (l + r) / 2; if (arr[m] - (m + 1) >= k) { find = m; r = m - 1; } else { l = m + 1; } } int preValue = find == 0 ? 0 : arr[find - 1]; int under = preValue - find; return preValue + (k - under);}
int main() { vector<int> arr = { 2, 3, 4, 7, 11 }; int k = 5; int result = findKthPositive(arr, k); cout << result << endl;}
复制代码
![2023-05-16：给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。 请你找到这个数组里第 k 个缺失的正整数。 输入：arr = [2,3,4,7,11], k = 5。 输出：9_golang_福大大架构师每日一题_InfoQ写作社区](https://static001.infoq.cn/static/infoq/img/logo-121-75.yuij86g.png){kind=logo}
评论