题目描述
Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.
Find the kth positive integer that is missing from this array.
Example1:
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.
Example2:
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
解题思路
- 模拟题，脑子别乱就好。
DP
class Solution {
public:
int findKthPositive(vector<int>& arr, int k) {
int pos = 1;
vector<int> res;
for(int i = 0; i < arr.size(); ){
// 需要时刻判断是否已经找到了第k个
if(res.size() < k && arr[i] != pos){
while(res.size() < k && arr[i] != pos){
res.push_back(pos);
pos++;
}
}else{
pos++;
i++;
}
}
// 如果此时走到了最后 还没有满足k个元素 需要往后面接着插入几个元素
if(res.size() <= k){
int t = arr[arr.size() - 1];
while(res.size() < k){
res.push_back(t + 1);
t++;
}
}
for(auto& i : res){
cout << i << endl;
}
return res[res.size() - 1];
}
};
