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的相关教程结束。