{"id":7212,"date":"2020-08-09T00:43:58","date_gmt":"2020-08-09T07:43:58","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7212"},"modified":"2020-08-09T01:28:51","modified_gmt":"2020-08-09T08:28:51","slug":"leetcode-1539-kth-missing-positive-number","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-1539-kth-missing-positive-number\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1539. Kth Missing Positive Number"},"content":{"rendered":"\n

Given an array arr<\/code> of positive integers sorted in a strictly increasing order<\/strong>, and an integer k<\/code>.<\/p>\n\n\n\n

Find the <\/em>kth<\/sup><\/code> positive integer that is missing from this array.<\/em><\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> arr = [2,3,4,7,11], k = 5\nOutput:<\/strong> 9\nExplanation: <\/strong>The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th<\/sup> missing positive integer is 9.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> arr = [1,2,3,4], k = 2\nOutput:<\/strong> 6\nExplanation: <\/strong>The missing positive integers are [5,6,7,...]. The 2nd<\/sup> missing positive integer is 6.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= arr.length <= 1000<\/code><\/li>
  • 1 <= arr[i] <= 1000<\/code><\/li>
  • 1 <= k <= 1000<\/code><\/li>
  • arr[i] < arr[j]<\/code> for 1 <= i < j <= arr.length<\/code><\/li><\/ul>\n\n\n\n
    Solution 1: HashTable<\/strong><\/h2>\n\n\n\n
    Store all the elements into a hashtable, and check from 1 to max(arr).<\/p>\n\n\n\n
    Time complexity: O(max(arr)) ~ O(1000)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int findKthPositive(vector& arr, int k) {\n    unordered_set s(begin(arr), end(arr));\n    for (int i = 1; i <= arr.back(); ++i) {\n      if (!s.count(i)) --k;\n      if (k == 0) return i;\n    }\n    return arr.back() + k;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Solution 2: Binary Search<\/strong><\/h2>\n\n\n\n
    We can find the smallest index l using binary search, s.t.
    arr[l] - l + 1 >= k
    which means we missed at least k numbers at index l.
    And the answer will be l + k.<\/p>\n\n\n\n
    Time complexity: O(logn)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int findKthPositive(vector& arr, int k) {\n    int l = 0;\n    int r = arr.size();\n    while (l < r) {\n      int m = l + (r - l) \/ 2;\n      if (arr[m] - (m + 1) >= k)\n        r = m;\n      else\n        l = m + 1;\n    }\n    return l + k;\n  }\n};\n<\/pre>\n\n<\/div>
    Java<\/h2>\n
    \n\n
    \nclass Solution {\n  public int findKthPositive(int[] arr, int k) {\n    int l = 0;\n    int r = arr.length;\n    while (l < r) {\n      int m = l + (r - l) \/ 2;\n      if (arr[m] - (m + 1) >= k)\n        r = m;\n      else\n        l = m + 1;\n    }\n    return l + k;\n  }\n}\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \nclass Solution:\n  def findKthPositive(self, arr: List[int], k: int) -> int:\n    l, r = 0, len(arr) \n    while l < r:\n      m = l + (r - l) \/\/ 2\n      if arr[m] - (m + 1) >= k:\n        r = m\n      else:\n        l = m + 1\n    return l + k\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given an array arr of positive integers sorted in a strictly increasing order, and an integer k. Find the kth positive integer that is missing from this array. Example 1: Input: arr…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[20,52,222,82],"class_list":["post-7212","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-array","tag-binary-search","tag-easy","tag-hashtable","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7212","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7212"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7212\/revisions"}],"predecessor-version":[{"id":7215,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7212\/revisions\/7215"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7212"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7212"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7212"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}