Teaching Kids Programming: Videos on Data Structures and Algorithms
You are given a list of non-negative integers nums. If there are exactly k numbers in nums that are greater than or equal to k, return k. Otherwise, return -1.
Constraints
1 ≤ n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [5, 3, 0, 9]
Output
3
Explanation
There are exactly 3 numbers that’s greater than or equal to 3: [5, 3, 9].Hint #1
Bucket sort, or can you binary search K?
Hint #2
sort the array then do binarysearch on k
Binary Search Algorithm: K Numbers Greater Than or Equal to K
We need to define a function to compute the number of elements that are greater than or equal to K. We can do this linear time:
1 2 3 4 5 6 | def f(k, nums): # O(N) ans = 0 for i in nums: if i >= k: ans += 1 return ans |
def f(k, nums): # O(N) ans = 0 for i in nums: if i >= k: ans += 1 return ans
Can we do better? We can sort and search in the reverse direction – exit the for check if the number is smaller than K – however, the complexity is still O(N) as it is still linear scan.
1 2 3 4 5 6 7 8 | nums.sort() # O(NLogN) def f(k, nums): ans = 0 for i in range(len(nums) - 1, -1, -1): if nums[i] < k: break ans += 1 return ans |
nums.sort() # O(NLogN) def f(k, nums): ans = 0 for i in range(len(nums) - 1, -1, -1): if nums[i] < k: break ans += 1 return ans
We can binary search using bisect_left to find out the insertion position/index if K is to insert in the list, and then compute the number of elements that are greater or equal to K. The time complexity is O(LogN).
1 2 3 | nums.sort() def f(k): return len(nums) - bisect.bisect_left(nums, k) |
nums.sort() def f(k): return len(nums) - bisect.bisect_left(nums, k)
With this in mind, we can then binary search the K value:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Solution: def solve(self, nums): nums.sort() left, right = 1, max(nums) def f(k): return len(nums) - bisect.bisect_left(nums, k) while left <= right: mid = (left + right) // 2 cur = f(mid) if cur == mid: return mid if cur < mid: right = mid - 1 else: left = mid + 1 return -1 |
class Solution: def solve(self, nums): nums.sort() left, right = 1, max(nums) def f(k): return len(nums) - bisect.bisect_left(nums, k) while left <= right: mid = (left + right) // 2 cur = f(mid) if cur == mid: return mid if cur < mid: right = mid - 1 else: left = mid + 1 return -1
The overall complexity is O(LogN+LogMLogN) where N is the number of length in the array, and M is the max(nums).
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: A Sample Job Resignation Letter - How to Resign?
Next Post: GoLang: Compute the Hamming Distance