前往
大廳
主題

LeetCode - 1608. Special Array With X Elements Greater Than or Equal X 解題心得

Not In My Back Yard | 2022-12-16 12:00:10 | 巴幣 100 | 人氣 267

題目連結:


題目意譯:
你被給定一非負整數陣列 nums。如果存在一整數 x 使得恰好有 x 個 nums 中的整數是大於或等於 x 的,則 nums 將被視為是「特殊的」。

注意到 x 不一定要是 nums 中的一個元素。

如果陣列是特殊的,則回傳 x 的值;反之,回傳 -1。可以證明如果 nums 是特殊的,x 值必定唯一。

限制:
1 ≦ nums.length ≦ 100
0 ≦ nums[i] ≦ 1000



範例測資:
範例 1:
輸入: nums = [3,5]
輸出: 2
解釋: 有 2 個數字(3 和 5)大於或等於 2。

範例 2:
輸入: nums = [0,0]
輸出: -1
解釋: 沒有數字 x 滿足要求。
如果 x = 0,應有 0 個數字 ≧ x,但是實際上有 2 個。
如果 x = 1,應有 1 個數字 ≧ x,但是實際上有 0 個。
如果 x = 2,應有 2 個數字 ≧ x,但是實際上有 0 個。
x 不能再更大了,因為 nums 中只有 2 個數字。

範例 3:
輸入: nums = [0,4,3,0,4]
輸出: 3
解釋: 有 3 個數字大於或等於 3。


解題思維:
這題類似,對答案進行二分搜尋法(Binary Search)即可。



假設我們現在猜的數字是 m,則我們可以直接掃過一次 nums,看有多少數字 ≧ m(假設有 C 個)。

可以看到如果 C = m,則這個 m 值即是題目要求的 x 值;如果 C > m,表示我們猜得太小了,應該猜更大的 m 值;最後如果 C < m,表示猜得太大,應該要猜更小的 m 值。

重複這個過程便可以找到題目要求的 x 值。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作