iT邦幫忙

2025 iThome 鐵人賽

DAY 10
0
自我挑戰組

從零開始學習LeetCode系列 第 10

Day10 Intersection of Two Arrays

  • 分享至 

  • xImage
  •  

題目:給定兩個整數陣列 nums1 和 nums2,請回傳它們的 交集(不重複元素)

  • 結果中的每個元素必須是唯一的,順序不重要。
  • https://ithelp.ithome.com.tw/upload/images/20250924/20169339mITEv63vFA.jpg

解法一
https://ithelp.ithome.com.tw/upload/images/20250924/201693396NCgC0gZQE.jpg

  • 雙層迴圈比對
  • 速度太慢

註解:

  • for i in nums1:逐一檢查 nums1 的每個元素
  • if i in nums2:檢查是否也存在於 nums2
  • i not in result:避免重複加入交集

理解:

  • 就像拿著 nums1 的元素,一個一個去 nums2 裡比對,看能不能找到一樣的數字

解法二
https://ithelp.ithome.com.tw/upload/images/20250924/20169339dwRHtRJdNK.jpg

  • Set 集合運算
  • Python 最推薦的方法

註解:

  • set(nums1):把 nums1 轉成集合,自動去除重複元素
  • &:集合的交集運算,取出共同元素
  • list(...):最後轉回列表

理解:

  • 就像兩張名單,先把重複的名字去掉,再找出名單裡同時出現的名字

解法三
https://ithelp.ithome.com.tw/upload/images/20250924/20169339zJCQKPMcVQ.jpg

  • 排序 + 雙指針
  • 可以在「不能用額外資料結構」的情況下使用

註解:

  • nums1.sort(), nums2.sort():先把兩個陣列排序
  • i, j:兩個指標,分別走訪 nums1 與 nums2
  • nums1[i] == nums2[j]:找到相同元素,加進 result(避免重複)
  • nums1[i] < nums2[j]:移動小的指標,避免錯過交集
  • 時間複雜度:O(n log n + m log m) → 取決於排序

理解:

  • 就像兩本排序好的字典,一邊翻一邊比對,如果字母一樣就記下來;如果不一樣,就翻動比較小的那一本

上一篇
Day9 Valid Anagram
下一篇
Day 11 Intersection of Two Arrays II
系列文
從零開始學習LeetCode11
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言