{"id":7456,"date":"2020-10-04T10:33:56","date_gmt":"2020-10-04T17:33:56","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7456"},"modified":"2020-10-04T10:43:19","modified_gmt":"2020-10-04T17:43:19","slug":"leetcode-1608-special-array-with-x-elements-greater-than-or-equal-x","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-1608-special-array-with-x-elements-greater-than-or-equal-x\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1608. Special Array With X Elements Greater Than or Equal X"},"content":{"rendered":"\n

You are given an array nums<\/code> of non-negative integers. nums<\/code> is considered special<\/strong> if there exists a number x<\/code> such that there are exactly<\/strong> x<\/code> numbers in nums<\/code> that are greater than or equal to<\/strong> x<\/code>.<\/p>\n\n\n\n

Notice that x<\/code> does not<\/strong> have to be an element in nums<\/code>.<\/p>\n\n\n\n

Return x<\/code> if the array is special<\/strong>, otherwise, return <\/em>-1<\/code>. It can be proven that if nums<\/code> is special, the value for x<\/code> is unique<\/strong>.<\/p>\n\n\n\n

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

Input:<\/strong> nums = [3,5]\nOutput:<\/strong> 2\nExplanation:<\/strong> There are 2 values (3 and 5) that are greater than or equal to 2.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [0,0]\nOutput:<\/strong> -1\nExplanation:<\/strong> No numbers fit the criteria for x.\nIf x = 0, there should be 0 numbers >= x, but there are 2.\nIf x = 1, there should be 1 number >= x, but there are 0.\nIf x = 2, there should be 2 numbers >= x, but there are 0.\nx cannot be greater since there are only 2 numbers in nums.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [0,4,3,0,4]\nOutput:<\/strong> 3\nExplanation:<\/strong> There are 3 values that are greater than or equal to 3.\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [3,6,7,7,0]\nOutput:<\/strong> -1\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= nums.length <= 100<\/code><\/li>
  • 0 <= nums[i] <= 1000<\/code><\/li><\/ul>\n\n\n\n
    Solution 1: Brute Force<\/strong><\/h2>\n\n\n\n
    Try all possible x from 0 to n.<\/p>\n\n\n\n
    Time complexity: O(n^2)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int specialArray(vector& nums) {\n    for (int x = 0; x <= nums.size(); ++x)\n      if (x == count_if(begin(nums), end(nums), [x](int num) { \n            return num >= x; }))\n        return x;\n    return -1;    \n  }\n};\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \n# Author: Huahua\nclass Solution:\n  def specialArray(self, nums: List[int]) -> int:\n    for x in range(len(nums) + 1):\n      if x == sum([n >= x for n in nums]): return x\n    return -1\n<\/pre>\n<\/div><\/div>\n\n\n\n
    Solution 2: Counting Sort<\/strong><\/h2>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(n)<\/p>\n\n\n\n
    f[i] := sum(nums >= i)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int specialArray(vector& nums) {\n    const int n = nums.size();\n    vector f(n + 2);\n    for (int v : nums) ++f[min(v, n)];\n    for (int i = n; i >= 0; --i)\n      if ((f[i] += f[i + 1]) == i) return i;\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given an array nums of non-negative integers. nums is considered special if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x. Notice that x does not have to…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[20,106,222],"class_list":["post-7456","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-brute-force","tag-easy","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7456","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=7456"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7456\/revisions"}],"predecessor-version":[{"id":7459,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7456\/revisions\/7459"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7456"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7456"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7456"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}