2023-05-16：给你一个严格升序排列的正整数数组 arr 和一个整数 k 。请你找到这个数组里第 k 个缺失的正整数。输入：arr = [2,3,

原创

福大大架构师每日一题

发布于 2023-05-16 13:17:14

29800

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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.如果当前位置arrm减去（m+1）大于等于k，说明第k个缺失的正整数在当前位置左侧，更新find为当前位置m，并把右指针r设为m-1，继续二分查找左半部分。

4.如果当前位置arrm减去（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;
}