1539. 第 k 个缺失的正整数
https://leetcode.cn/problems/kth-missing-positive-number/
难度简单106
给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。
请你找到这个数组里第 k 个缺失的正整数。
示例 1：
输入：arr = [2,3,4,7,11], k = 5 输出：9 解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。
示例 2：
输入：arr = [1,2,3,4], k = 2 输出：6 解释：缺失的正整数包括 [5,6,7,...] 。第 2 个缺失的正整数为 6 。
提示：
1 <= arr.length <= 10001 <= arr[i] <= 10001 <= k <= 1000- 对于所有
1 <= i < j <= arr.length的i和j满足arr[i] < arr[j]
通过次数25,597提交次数47,444
class Solution {
public int findKthPositive(int[] arr, int k) {
// 缺失数在数组外的
int n = arr.length-1;
if((arr[n]-n-1)<k) return k-(arr[n]-n-1)+arr[n];
if(arr[0]>k) return k;
//缺失数在数组内的：二分查找
int start = 0;
int end = arr.length-1;
int mid;
while(start<=end)
{
mid = (end-start)/2+start;
if(arr[mid]-mid-1==k && arr[mid+1]-mid-2>=k)
{
System.out.println(mid+" "+arr[mid]);
int num = arr[mid]-mid-1-k;
System.out.println("num="+num);
int x = arr[mid]-1;
while(num>=0)
{
if(x==arr[mid-1])
{
x--;
}
else num--;
}
return x;
}
if(arr[mid]-mid-1<k && arr[mid+1]-mid-2>=k)
{
System.out.println(mid+1+" "+arr[mid+1]);
return arr[mid+1]-(arr[mid+1]-mid-2-k+1);
}
if(arr[mid]-mid-1>k) end = mid-1;
else start=mid+1;
}
return 0;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/69088.html
