第k个缺少正整数

Question

给定一个按严格递增顺序排序的正整数数组arr和一个整数k。

查找此数组中缺少的第k个正整数。

示例1：

输入：arr=[2,3,4,7,11]，k=5输出：9说明：缺少的正整数是[1,5,6,8,9,10,12,13，…]。第五个缺失的正整数是9。示例2：

输入：arr=[1,2,3,4]， k=2输出：6解释：缺少的正整数是[5,6,7，...]。第二个缺失的正整数是6。

约束条件：

1.

1.

1.

arr[i]

我已经提交了这段代码，但这显示了TLE错误。请解释TLE发生的原因以及如何解决此问题。

    class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        vector<int> ans;
        int count=0,i=1,flag=0;
        
        while(count<k)
        {
            int start=0,end=arr.size()-1;
            while(start<=end)
            {
                int mid=start+(end-start)/2;
                if(arr[mid]==i) 
                    flag=1;
                else if(arr[mid]>i) 
                    end=mid-1; 
                else 
                    start=mid+1;

            }
            if(flag==0)
            {
                ans.push_back(i); 
                count++;
            }
            i++;
        } 
        return ans[k-1];
    }
};

Answer 1

你可以做一个桶，因为这些约束表明了这一点。

vector<int> sorted_array;

int bucket[1000];

for (int i=0;i<1000;i++)
{
  bucket[i] = 0;
}

for (auto elem : sorted_array)
{
  bucket[elem]++;
}

int k = <user_input>;

int result = -1;
int index = 0;
for (int i=0;i<1000;i++)
{
  if (bucket[i] == 0) // missing
  {
    index++;
  }
  if (index == k)
  {
    result = i;
    break;
  }
}

if (result > 0)
{
   cout << "We have a result: " << result << endl;
}
else
{
   cout << "No result found\n";
}

Answer 2

匿名用户

您正在一次又一次地开始新的二进制搜索。

相反，您需要计算a[i]和i之间的差值，并将此差值与k进行比较-因此，只需要对给定的k进行唯一的循环，唯一的二进制搜索，时间是对数的

Python代码，但我希望它可以理解：

def findit(a, n, k):
    if a[0] > k:
        return k
    if k > a[n-1] - n:
        return k + a[n-1] - n-1

    #binary search of index of first occurrence of the least element   greater than key 
    start = 0
    end = n - 1
    while start <= end:
        mid = (start + end) // 2
        t = a[mid] - mid
        if t <= k:
            start = mid + 1
        else:
            idx = mid
            end = mid - 1
    return(k + idx)

a = [2,3,4,7,11]
for k in range(1, 9):
    print(findit(a, len(a), k))

result    
1   5   6   8   9   10   12   13

Answer 3

代码中至少有两个问题。

首先，对于导致无限循环的每个循环，标志不会重置为0

其次，当在数组中找到一个数字时，代码也会卡在while循环中，因为没有中断语句。

下面是一个有效的代码。我在循环中移动了标志声明，并在向量中找到一个数字时添加了一个break语句。

#include <iostream>
#include <vector>

using namespace std;


class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        vector<int> ans;
        int count=0,i=1;
        
        while(count<k)
        {
            int start=0,end=arr.size()-1,flag=0;
            while(start<=end)
            {
                int mid=start+(end-start)/2;
                if(arr[mid]==i) {
                    flag=1;
                    break;
                }
                else if(arr[mid]>i) 
                    end=mid-1; 
                else 
                    start=mid+1;

            }
            if(flag==0)
            {
                ans.push_back(i); 
                count++;
            }
            i++;
        } 
        return ans[k-1];
    }
};

int main() {

  std::cout << "Hello" << std::endl;
  Solution a;
  vector<int> testv = {2, 3, 4, 7, 11 };
  std::cout << a.findKthPositive(testv, 5) << std::endl;
}