问题:
给定一个升序数组,求第k个该数组缺失的数。
Example 1: Input: arr = [2,3,4,7,11], k = 5 Output: 9 Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9. Example 2: Input: arr = [1,2,3,4], k = 2 Output: 6 Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6. Constraints: 1 <= arr.length <= 1000 1 <= arr[i] <= 1000 1 <= k <= 1000 arr[i] < arr[j] for 1 <= i < j <= arr.length
解法:
解法一:二分查找(Binary Search)
找到arr[m]之前缺失数字个数arr[m]-(m+1),若>=k,
那要找的缺失数为:已有的数(未缺失)+缺失的第k个=m+k
代码参考:
1 class Solution { 2 public: 3 int findKthPositive(vector<int>& arr, int k) { 4 int l = 0, r = arr.size(); 5 while(l<r) { 6 int m = l+(r-l)/2; 7 int count = arr[m]-m-1; 8 if(count>=k) { 9 r = m; 10 } else { 11 l = m+1; 12 } 13 } 14 return l+k; 15 } 16 };
解法二:hash
将已有的数字,存入unordered_set中,
从1开始轮询每个数字,若没有在已有的数字列表中,
k--,说明该数字是漏掉的数字。漏掉数字总数-1。
直到k=0,当前数字则是要找的漏掉的第k个数字。返回。
♻️ 优化,在轮询到已有数字列表的最后一个时,k还没减完,
则直接返回最后一个数字+当前剩下的k。
代码参考:
1 class Solution { 2 public: 3 int findKthPositive(vector<int>& arr, int k) { 4 int res=0; 5 unordered_set<int> arrset(arr.begin(), arr.end()); 6 for(int i=1; i<=arr.back(); i++) { 7 if(arrset.count(i)==0) k--; 8 if(k==0) return i; 9 } 10 return arr.back()+k; 11 } 12 };