https://leetcode.com/problems/single-number-iii 260. Single Number III 給定一數列 此數列只有兩個數字單獨出現 其他元素都成雙成對 請回傳單獨出現的兩個數字 Example 1: Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] is also a valid answer. Example 2: Input: nums = [-1,0] Output: [-1,0] Example 3: Input: nums = [0,1] Output: [1,0] Constraints: 2 <= nums.length <= 3 * 104 -231 <= nums[i] <= 231 - 1 Each integer in nums will appear twice, only two integers will appear once. 思路: 哈希表紀錄出現次數 Python Code: class Solution: def singleNumber(self, nums: List[int]) -> List[int]: res = [] map = defaultdict(int) for n in nums: map[n] += 1 for k,v in map.items(): if v == 1: res.append(k) if len(res) == 2: return res 應該有位運算解法 但我試不出來 告辭 -- ※ 發信站: 批踢踢實業坊(ptt-website.tw), 來自: 114.43.156.128 (臺灣) ※ 文章網址: https://ptt-website.tw/Marginalman/M.1717127432.A.61B
DJYOSHITAKA: 別捲了05/31 11:51
wwndbk: 大師 05/31 11:53
argorok: 大師 05/31 11:53
JIWP: 你就先所有數xor一次 05/31 11:54
JIWP: 接著找出這個結果哪一個位元是1 05/31 11:54
Muzaffer: 包養不急於談感情。 05/31 11:54
JIWP: 代表這兩個數在這個位元一個是1一個是0 05/31 11:54
JIWP: 再來你就依照這個位元去把nums的元素分成兩堆 05/31 11:55
JIWP: 最後將這兩堆分別xor就可以得到答案了 05/31 11:56
JIWP: 分成該位元分別是1、0的兩堆 05/31 11:57
sustainer123: 我試試 05/31 11:58
MIJice: 包養網結交志同道合。 05/31 11:58
sustainer123: 可是這樣怎麼感覺時間複雜度還不如計數 05/31 11:59
JIWP: 時間複雜度就O(N) 05/31 11:59
JIWP: 主要是題目要求不能用extra space 05/31 12:00
sustainer123: 原來 05/31 12:05