leetcode1539 第k个缺失的正整数

思路1：

暴力枚举。

实现1：

 1 class Solution
 2 {
 3 public:
 4     int findKthPositive(vector<int>& arr, int k)
 5     {
 6         int n = arr.size();
 7         vector<int> cnt(2001, 0);
 8         for (int i = 0; i < n; i++) cnt[arr[i]] = 1;
 9         int x = 0, res = 0;
10         for (int i = 1; i <= 2000; i++)
11         {
12             if (!cnt[i]) x++;
13             if (x == k) { res = i; break; }
14         }
15         return res;
16     }
17 };

思路2:

根据数组中元素的数值大小和所在位置的相对关系计算答案。

实现2:

 1 class Solution
 2 {
 3 public:
 4     int findKthPositive(vector<int>& arr, int k)
 5     {
 6         if (arr[0] > k) return k;
 7         int cnt = arr[0] - 1, n = arr.size();
 8         for (int i = 0; i < n - 1; i++)
 9         {
10             int d = arr[i + 1] - arr[i] - 1;
11             if (cnt + d >= k) return arr[i] + k - cnt;
12             cnt += d;
13         }
14         return arr[n - 1] + k - cnt;
15     }
16 };

思路3:

在思路2的基础上更进一步，使用二分查找。

实现3:

 1 class Solution
 2 {
 3 public:
 4     int cnt(vector<int>& arr, int m)
 5     {
 6         return arr[m] - m - 1;
 7     }
 8     int findKthPositive(vector<int>& arr, int k)
 9     {
10         int n = arr.size();
11         int tmp = arr[n - 1] - n;
12         if (tmp < k) return arr[n - 1] + k - tmp;
13         int l = 0, r = n - 1, p = -1;
14         while (l <= r)
15         {
16             int m = l + r >> 1;
17             if (arr[m] - m - 1 < k) l = m + 1;
18             else
19             {
20                 p = m; r = m - 1;
21             }
22         }
23         tmp = arr[p] - p - 1;
24         return arr[p] + k - tmp - 1;
25     }
26 };