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