頭角崢嶸 恰好k個元素大於等於k_Leetcode #1608 排序/二分搜尋 應用

Xiang Lee on Unsplash

題目敘述

給定一個輸入非負整樹陣列nums，請找出k值，使得陣列中恰好有k個元素 大於等於 k。

無果無解，回傳-1。

原文題目敘述

測試範例

Example 1:

Input: nums = [3,5]
Output: 2
Explanation: There are 2 values (3 and 5) that are greater than or equal to 2.

Example 2:

Input: nums = [0,0]
Output: -1
Explanation: No numbers fit the criteria for x.
If x = 0, there should be 0 numbers >= x, but there are 2.
If x = 1, there should be 1 number >= x, but there are 0.
If x = 2, there should be 2 numbers >= x, but there are 0.
x cannot be greater since there are only 2 numbers in nums.

Example 3:

Input: nums = [0,4,3,0,4]
Output: 3
Explanation: There are 3 values that are greater than or equal to 3.
輸入陣列裡，恰好有3個元素大於等於3​

約束條件

Constraints:

• 1 <= nums.length <= 100

輸入陣列長度介於1~100之間。

• 0 <= nums[i] <= 1000

每個陣列元素值都介於0~1000之間。

觀察

恰好k個元素 >= k，找出k值。

k值最小可能是1，最大可能是n = len(nums)，因為陣列裡最多也才n個元素。

演算法

怎麼找k值?

如果陣列由小到大排序好，那麼可以從左到右掃描每個元素，k值從n到1逐次遞減去檢查，假如有某一次疊代剛好發現有k個元素 >= k，那麼當下的k值就是答案；如果最後都不滿足，無解回傳-1。

如果陣列沒有排序好，那麼可以用二分搜尋法，從下邊界1和上邊界n去砍半夾擠k值，如果某回合剛好發現有k個元素素 >= k，那麼當下的k值就是答案；如果最後都不滿足，無解回傳-1。

程式碼 排序法

# Option_#1: Sorting

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        
        # Keep nums sorted in ascending order
        nums.sort()

        n = len(nums)

        if nums[0] >= n:
            # First element is smaller than or equal to n
            # There are exactly n elements larger than or equal to n
            return n

        for i in range(1, n):
            
            # Number of elements on index from i to n-1
            counting = n-i

            if nums[i-1] < counting <= nums[i]:
                # Exact element on i-th index  is larger than or equal to counting
                # There are exactly counting elements (from i-th index to n-1 th index) larger than or equal to counting
                return counting

        return -1

程式碼 二分搜尋法

# Option_#2: Binary search
class Solution:
    def specialArray(self, nums: List[int]) -> int:
        
        def check(k):
            # Counting how many number >= k
            return sum( 1 for number in nums if number >= k )
        # ------------------------------------------

        # Launch binary search to find k, such that there are exactly k number >= k in input array.
        lower, upper = 1, len(nums)

        while lower <= upper:

            mid = lower + (upper - lower)//2

            count_of_larger_equal = check(k=mid)
            if  count_of_larger_equal == mid:
                return mid

            elif count_of_larger_equal > mid:
                # mid is too small
                # try larger next round
                lower = mid+1
            
            else:
                # mid is too large
                # try smaller nexr round
                upper = mid-1
        
        return -1

複雜度分析

時間複雜度: O( n log n)

排序法排序耗費O(n log n)，接著線性掃描耗費O(n)，總時間成本依然為O(n log n)

二分搜尋法外層耗費O( log n)，內層線性掃描耗費O(n)，總時間成本為O( n log n)

空間複雜度: O(1)

兩種方法所用到的皆為固定尺寸的臨時變數，皆為常數級別O(1)。

關鍵知識點

如果解空間具有遞增或遞減的性質(近似於已排序)，可以用二分搜尋法加快搜尋效率。

Reference

[1] Special Array With X Elements Greater Than or Equal X - LeetCode