作者sustainer123 (caster)
標題Re: [閒聊] 每日leetcode
時間2024-05-31 11:50:29
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