題目連結:
題目意譯:
你被給定一非負整數陣列 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 值。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。