给你一个 严格升序排列 的正整数数组 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 <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-missing-positive-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
package cn.fansunion.leecode.number;
/**
* 1539. 第 k 个缺失的正整数 给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。
*
* 请你找到这个数组里第 k 个缺失的正整数。 力扣
*
* @author [email protected]
*
* 2022-2-19
*/
public class KthMissingPositiveNumber {
/* 示例 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 <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j]
*/
/**
* 思路：从1到x遍历数组，数组中找到当前n值，就下一个；找不到，漏掉+1；<br/>就网上的很多代码，可读性差的要死
* @param arr
* @param k
* @return
*/
public int findKthPositive(int[] arr, int k) {
//漏掉的数目
int skip = 0;
//数组中的元素，匹配到的个数（下标，逐步向后，但不一定每一次都命中-向后移）
int arrMatchIndex = 0;
//n<=1000不对，改成了“arr.length+k”，不一定非常精确
for (int n = 1; n <= arr.length+k; n++) {
//arr越界了，漏掉的数字+1
if (arrMatchIndex >= arr.length) {
skip++;
} else {
//arr没越界，数字不相等，漏掉的数字+1
if (n == arr[arrMatchIndex]) {
arrMatchIndex++;
} else {
skip++;
}
}
//漏掉第k次，n就是那个数字
if (skip == k) {
return n;
}
}
return -1;
}
}
package test.leecode.number;标签：arr,正整数,int,3626,test,new,缺失 From： https://blog.51cto.com/fansunion/6056788
import org.junit.Assert;
import org.junit.Test;
import cn.fansunion.leecode.number.KthMissingPositiveNumber;
/**
* @author [email protected]
*
* 2022-2-25
*/
public class KthMissingPositiveNumberTest {
@Test
public void test() {
KthMissingPositiveNumber test = new KthMissingPositiveNumber();
int[] nums59=new int[] {2,3,4,7,11};
Assert.assertEquals(9,test.findKthPositive(nums59,5));
int[] nums26=new int[] {1,2,3,4};
Assert.assertEquals(6,test.findKthPositive(nums26,2));
int[] nums36=new int[] {1,3,5,7,9,11};
Assert.assertEquals(6,test.findKthPositive(nums36,3));
int[] nums1219=new int[] {1,3,5,7,9,11,18};
Assert.assertEquals(19,test.findKthPositive(nums1219,12));
}
}