iT邦幫忙

2025 iThome 鐵人賽
DAY 13
0
自我挑戰組

Java × LeetCode-30天日記系列 第 13 篇

Day 13：Majority Element (LC #169)

17th鐵人賽
50 瀏覽

  • 分享至 

  • xImage
    •  

題目理解
我的理解 : 給定一個大小為 n 的整數陣列 nums，找出其中出現次數大於 n/2 的元素。
方法
Boyer-Moore 投票算法

  • 設一個候選數 candidate 和一個計數器 count。
  • 如果 count == 0，更新 candidate = num。
  • 如果 num == candidate，count++；否則 count--。
    https://ithelp.ithome.com.tw/upload/images/20250926/20169238Al9Tgb4a53.png

心得
Boyer-Moore 投票演算法巧妙地利用「抵消」這個概念，把一個看似需要計數統計的問題，簡化成僅需 O(1) 空間的解法，雖然第一次看會覺得有點「神奇」，但理解成「大數吃掉小數，最後一定剩下大數」就會非常直觀。


上一篇
Day 12：LRU Cache (LC #146) ➝ LinkedHashMap應用
下一篇
Day 14：Contains Duplicate (LC #217)
系列文
Java × LeetCode-30天日記 共 16 篇
  1. 12
    Day 12：LRU Cache (LC #146) ➝ LinkedHashMap應用
  2. 13
    Day 13：Majority Element (LC #169)
  3. 14
    Day 14：Contains Duplicate (LC #217)
  4. 15
    Day 15：Binary Search (LC #704)
  5. 16
    Day 16：Search Insert Position (LC #35)
完整目錄
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
iThome鐵人賽
參賽組數
902 組
團體組數
37 組
累計文章數
13926 篇
完賽人數
152 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 17th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react
熱門問題
熱門回答
熱門文章
IT邦幫忙