ETH官方钱包

前往
大廳
主題

LeetCode - 2150. Find All Lonely Numbers in the Array 解題心得

Not In My Back Yard | 2022-09-02 12:00:08 | 巴幣 0 | 人氣 158

題目連結:


題目意譯:
你被給定一整數陣列 nums。當一數 x 只出現一次,且鄰近數字(即,x + 1 和 x - 1)也沒有出現於陣列中時,我們稱其為落單。

回傳所有 nums 中落單的數字。你可以按任意順序回傳答案。

限制:
1 ≦ nums.length ≦ 10 ^ 5
0 ≦ nums[i] ≦ 10 ^ 6



範例測資:
範例 1:
輸入: nums = [10,6,5,8]
輸出: [10,8]
解釋:
- 10 是一個落單的數字,因為它只出現一次且 9 和 11 沒有出現於 nums 中。
- 8 是一個落單的數字,因為它只出現一次且 7 和 9 沒有出現於 nums 中。
- 5 不是一個落單的數字,因為 6 有出現於 nums 中。反之亦然(譯注:此指 6 也是不孤單的數字)。
因此,nums 中的落單數字為 [10, 8]。
注意,我們也可以回傳 [8, 10]。

範例 2:
輸入: nums = [1,3,5,3]
輸出: [1,5]
解釋:
- 1 是一個落單的數字,因為它只出現一次且 0 和 2 沒有出現於 nums 中。
- 5 是一個落單的數字,因為它只出現一次且 4 和 6 沒有出現於 nums 中。
- 3 不是落單的數字,因為它出現了兩次。
因此,nums 中的落單數字為 [1, 5]。
注意,我們也可以回傳 [5, 1]。


解題思維:
直接先將 nums 排序便可以很簡單就看出有哪些數字是落單的。因為如果一數 x 是落單的,則由小到大排序後排於其左側之數字(如果有的話)將會小於 x - 1,而且排於其右側之數字(如果有的話)將會大於 x + 1。

因此根據以上判斷方式便可以在排序之後掃過一次 nums 便找出所有落單數字,即所求。




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

創作回應

更多創作