2023-05-16：給你一個 嚴格升序排列 的正整數(shù)數(shù)組 arr 和一個整數(shù) k 。 請你找到這個
2023-05-16：給你一個 嚴格升序排列 的正整數(shù)數(shù)組 arr 和一個整數(shù) k 。
請你找到這個數(shù)組里第 k 個缺失的正整數(shù)。
輸入：arr = [2,3,4,7,11], k = 5。
輸出：9。
答案2023-05-16：
大體步驟如下：
1.初始化左指針l為0，右指針r為數(shù)組長度減一，定義中間指針m和find（找到第k個正整數(shù)前的下標位置），并將find初始化為數(shù)組長度。
2.當左指針小于等于右指針時，執(zhí)行二分查找。令m等于左指針和右指針之間的中間值。（注：這里取中間值可以使用位運算優(yōu)化）。
3.如果當前位置arr[m]減去（m+1）大于等于k，說明第k個缺失的正整數(shù)在當前位置左側(cè)，更新find為當前位置m，并把右指針r設(shè)為m-1，繼續(xù)二分查找左半部分。
4.如果當前位置arr[m]減去（m+1）小于k，說明第k個缺失的正整數(shù)在當前位置右側(cè)，把左指針l設(shè)為m+1，繼續(xù)二分查找右半部分。
5.查找結(jié)束后，如果find等于0，說明要找的是第一個缺失的正整數(shù)，返回0即可；否則，找到第k個正整數(shù)前的一個位置，把這個位置上的元素賦值給preValue，計算從當前位置到第k個正整數(shù)的缺失數(shù)量under，最終結(jié)果就是preValue加上k減去under的值。
6.返回結(jié)果。
時間復(fù)雜度為O(logn)，其中n是數(shù)組的長度。因為代碼采用了二分查找的算法，每次查找可以將搜索范圍縮小一半，所以時間復(fù)雜度為O(logn)。
空間復(fù)雜度為O(1)，因為代碼只使用了常數(shù)個變量來存儲中間結(jié)果，與輸入數(shù)據(jù)的規(guī)模大小無關(guān)。因此，空間復(fù)雜度為常數(shù)級別。
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;
}
福大大架構(gòu)師每日一題
java當死，golang當立。最新面試題，涉及golang，rust，mysql，redis，云原生，算法，分布式，網(wǎng)絡(luò)，操作系統(tǒng)。
公眾號
