iT邦幫忙

2025 iThome 鐵人賽

DAY 15
0
自我挑戰組

Leetcode 自學系列 第 15

自學Leetcode Day15

  • 分享至 

  • xImage
  •  

260. Single Number III
1.題目說明:給定一個整數陣列 nums,其中正好有兩個元素只出現一次,其餘的元素都出現了兩次。請找出這兩個只出現一次的元素。
要求:

  • 時間複雜度為 O(n)(線性)
  • 空間複雜度為 O(1)(常數)
    2.解法思路(使用位運算)
    這題的巧妙解法是利用 位元 XOR(^) 的特性來完成:
    3.XOR 性質:
  • a ^ a = 0
  • a ^ 0 = a
  • XOR 運算具有交換律與結合律
    4.步驟如下:
    1.先把所有數字 XOR 起來,最後會得到 a ^ b(因為其他成對的數字都會變成 0 被抵消)。
    2.a ^ b 的結果不為 0,表示 a 和 b 至少有一個位元不同(也就是 1)。
    3.找到這個 XOR 結果中 任意一個為 1 的位元位置(我們通常找最右邊的 1)。
    4.用這個位元來將原陣列的數字分成兩組:
    • 一組這個位元是 0
    • 一組這個位元是 1
      5.在這兩組中,各自再做一次 XOR,就能分別得到 a 和 b。
      5.範例輸入輸出
      輸入:nums = [1,2,1,3,2,5]
      執行流程:
  • XOR 所有數字得:3 ^ 5 = 6
  • 找出 6 最右邊的 1 → diff = 2
  • 分組後 XOR:
    • 組一:1, 1, 2, 2 → XOR = 0
    • 組二:3, 5 → XOR = 3 和 5
      輸出:[3, 5]
      6.程式碼截圖:https://ithelp.ithome.com.tw/upload/images/20250929/20169241erHIo4Xsk8.png
      7.學習心得:此次題目我自認為比較難,但這也是給我一個學習的機會,從AI問答中學習到這題的學習重點,之後還是會找類似的題目去做練習。

上一篇
自學Leetcode Day14
下一篇
自學Leetcode Day16
系列文
Leetcode 自學16
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言