前往
大廳
主題

LeetCode - 1365. How Many Numbers Are Smaller Than the Current Number 解題心得

Not In My Back Yard | 2023-03-06 12:00:09 | 巴幣 0 | 人氣 124

題目連結:


題目意譯:
給定陣列 nums,對於每個 nums[i] 找到在陣列中小於其值的數字數量為何。也就是說,對於每個 nums[i] 你必須統計合法索引值 j 的數量滿足 j != i 且 nums[j] < nums[i]。

以一陣列之形式回傳答案。

限制:
2 ≦ nums.length ≦ 500
0 ≦ nums[i] ≦ 100



範例測資:
範例 1:
輸入: nums = [8,1,2,2,3]
輸出: [4,0,1,1,3]
解釋:
對於 nums[0]=8 存在著四個小於其值的數字(1 、 2 、 2 和 3)。
對於 nums[1]=1 不存在著小於其值的數字。
對於 nums[2]=2 存在著一個小於其值的數字(1)。
對於 nums[3]=2 存在著一個小於其值的數字(1)。
對於 nums[4]=3 存在著三個小於其值的數字(1 、 2 和 2)。

範例 2:
輸入: nums = [6,5,4,8]
輸出: [2,1,0,3]

範例 3:
輸入: nums = [7,7,7,7]
輸出: [0,0,0,0]


解題思維:
將 nums 複製一份,稱其為 sorted,然後將 sorted 中的數字由小排到大。

接著掃過一次 nums,對於每個數字 nums[i] 去 sorted 中利用二分搜尋法(Binary Search)來找到 nums[i] 位於的 sorted 中的何處,且該索引值應為最小(因為有可能有多個數字與 nums[i] 相同)。

假設 nums[i] 是位於 sorted[j],而索引值 j 即代表著前面有 j 個小於 nums[i] 的數字存在。

將所有 nums[i] 的答案找出來之後存成一陣列便是所求。




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

創作回應

更多創作