iT邦幫忙

2025 iThome 鐵人賽

DAY 11
0
自我挑戰組

從零開始學習LeetCode系列 第 11

Day 11 Intersection of Two Arrays II

  • 分享至 

  • xImage
  •  

題目:給定兩個整數陣列 nums1 和 nums2,請回傳它們的 交集。

  • 這次允許重複元素,交集中每個元素出現的次數應該與兩個陣列中最小出現次數相同
  • 結果的順序不重要
  • https://ithelp.ithome.com.tw/upload/images/20250925/20169339ABeKuNCF6s.jpg

解法一
https://ithelp.ithome.com.tw/upload/images/20250925/20169339H5TdLWWzdF.jpg

  • 兩兩比對,移除匹配元素
  • 適合小數據量練習

註解:

  • nums2_copy = nums2[:]:建立 nums2 的副本,避免修改原始陣列
  • if num in nums2_copy:檢查 nums1 的元素是否在 nums2 中
  • nums2_copy.remove(num):移除已匹配的元素,避免多次匹配

理解:

  • 就像拿 nums1 的每個數字去 nums2 找,如果找到了就拿走一個,下一個相同數字還能繼續找

解法二
https://ithelp.ithome.com.tw/upload/images/20250925/20169339n0jCTFM3EK.jpg

  • Counter 統計出現次數
  • 快速、實戰推薦

註解:

  • Counter(nums1):統計 nums1 每個元素出現次數
  • min(count1[num], count2[num]):取兩個陣列中元素出現的最小次
  • result.extend([...]):把相同元素加入結果

理解:

  • 就像做兩個數字清單的「計數表」,每個數字出現幾次都知道,交集就取次數少的那個

解法三
https://ithelp.ithome.com.tw/upload/images/20250925/20169339mxCNxnbFws.jpg

  • 排序 + 雙指針比對
  • 不能用額外資料結構時使用

註解:

  • nums1.sort(), nums2.sort():排序方便雙指針比對
  • i, j:兩個指標分別走訪 nums1 和 nums2
  • nums1[i] == nums2[j] → 找到交集,加入結果
  • nums1[i] < nums2[j] → 移動較小指標

理解:

  • 就像翻兩本已排序的字典,字母一樣就記下,字母小的先翻下一頁,重複元素會自動被加入

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

尚未有邦友留言

立即登入留言