1539. Kth Missing Positive Number

難度: Easy

類型: Array, Binary Search, Biweekly Contest 32

CPP程式下載: 1539.cpp

前情題要:

尋找第K個遺漏的正整數。

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Return the kth positive integer that is missing from this array.

 

Example 1:

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.

Example 2:

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

Follow up:

Could you solve this problem in less than O(n) complexity?

思考方式:

1.正整數是連續的, 如果有漏掉就不連續了。

2.如果Array第五個值(index=4)是5, 就代表前面都是連續沒有漏掉。那下次從第六個值開始找, 找漏掉 K 個數。

3.如果Array第五個值是7, 就代表前面漏掉兩個數。那下次從第六個值開始找, 找漏掉 K-2 個數。

4.如果Array第K個值是K, 就代表前面連續沒漏掉。那下次從第K+1個值開始找, 找漏掉 K 個數。

5.如果Array第K個值是2K-1, 就代表前面漏掉K-1個數。那下次就從第K+1個值開始找, 找漏掉 1 個數。

6.如果Array第K個值是2K, 就代表前面漏掉K個數。那就要從Array的頭開始找。

結論: 每次跳K個index取值來看, 如果都連續就再跳K個。如果不連續就看這個值有沒有大於等於2K, 有就從這次的開頭開始找, 最多不用K次就會找到。如果這個值沒有大於2K, 就把K值減掉已發現漏掉的個數。用新的K值再往後找K個, 以此類推。

複雜度思考:

Time Complexity: Worst case: O( N ), Best Case: O(N/K)

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 13.16 MB, Beats: 90.26%

Accepted

87 / 87 testcases passed

tendchen

submitted at Aug 05, 2025 14:40

Runtime

0ms

Beats100.00%

Analyze Complexity

Memory

13.16MB

Beats90.26%

Analyze Complexity

Code

C++

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
      
       int next_num=k, next_index=k-1;
       int arr_size=arr.size();
       //cout << "arr_size=" << arr_size <<"\n";
       //cout << "k=" << k <<"\n";
       int rest_arry_size=arr_size;
       
       while (1)
       {
            
            if ((k<=rest_arry_size)&&(next_index<arr_size))
            {
                if (arr[next_index]==next_num)
                {
                    next_index+=k;
                    next_num+=k;
                    rest_arry_size-=k;
                    continue;
                }
                else if ((arr[next_index]-next_num)<k)
                {
                    k=k-(arr[next_index]-next_num);
                    //cout << "k1=" << k <<"\n";
                    //cout << "arr["<<next_index<<"]=" << arr[next_index] <<"\n";
                    //cout << "next_num=" << next_num <<"\n";
                    next_num=arr[next_index]+k;
                    next_index+=k;
                    rest_arry_size-=k;
                    continue;                   
                }
                else
                {
                    //next_index-=(k-1);
                    //next_num-=(k-1);
                    break;
                }
            }
            else
            {
                //next_index-=(k-1);
                //next_num-=(k-1);
                break;
            }
       }
       //cout << "k=" << k << "\n";
       next_index-=(k-1);
       next_num-=(k-1);
       //cout << "next_index=" << next_index << "\n";
       //cout << "next_num=" << next_num << "\n";
       for (int i=next_index;;i++)
       {
            if (i==arr_size)
            {
                return arr[arr_size-1]+k;
            }
            if (arr[i]==next_num)
            {
                next_num++;
                continue;
            }
            else
            {
                if ((arr[i]-next_num)>=k)
                {
                    return (next_num+k-1);
                }
                else
                {
                    k=k-(arr[i]-next_num);
                    next_num=arr[i]+1;
                }
            }
       }
    }
};