java - 查找连续数组中的第 k 个缺失元素(超出时间限制)

Question

给定一个递增序列 a[]，我们需要找到递增序列中不存在的第 K 个缺失的连续元素。如果没有第 k 个缺失元素，则输出 -1。

第一行由一个整数T组成，即测试用例的数量。每个测试用例的第一行由两个整数 N 和 K 组成。下一行由 N 个间隔的整数组成。

输入

5 2

1 3 4 5 7

输出 6

因为第一个缺失元素是 2，第二个(第 k 个)缺失元素是 6。

我收到运行时错误运行时错误: 以下解决方案超出了运行时错误时间限制:

while(t > 0){
    int n = sc.nextInt();
    int k = sc.nextInt();
    int a[] = new int[n];
    int b[] = new int[n];
    for(int i=0;i<n;i++){
        a[i] = sc.nextInt();
    }
    int sub=0;
    for(int i=0;i<n-1;i++){
       for(int j=0;j<n;j++){ 
        sub = a[i+1] - a[i];
        if(sub != 1){
            b[j] = a[i] + 1;
        }
      } 
    }

    if(b[0]==0)
        System.out.println(-1);
    else  
        System.out.println(b[k-1]);

    t--;
}

我无法弄清楚如何减少循环并提高运行时复杂性。谁能帮我看看该怎么做。

Answer 1

 public void findNthMissingNum(int[] nums,int n){

    int low = 0;
    int high = nums.length - 1;

    while(low  < high){
        if(high - low == 1){
            System.out.println(nums[low]+n);
            break;
        }
        int mid = low + (high - low)/2;

        int missingOnLeft = nums[mid] - nums[low] - 1;
        int presentOnLeft = mid - low - 1;

        if(n > missingOnLeft - presentOnLeft){
            //go right
            low = mid;
            n -= (missingOnLeft - presentOnLeft);
        }else{
            //go left
            high = mid;

        }

    }
}