題目連結:
題目意譯:
給定一個大小為 n 的陣列,找出其中的主要元素。主要元素指的是出現次數超過 ⌊ n/2 ⌋ 的元素。
你可以假設陣列非空,且主要元素保證存在。
範例測資:
範例 1:
輸入: [3,2,3]
輸出: 3
範例 2:
輸入: [2,2,1,1,1,2,2]
輸出: 2
解題思維:
還記得「戰鬥」演算法(正式名稱為摩爾多數投票演算法,Boyer–Moore majority vote algorithm)嗎?參見
此題。
特別的是,這題保證一定有主要元素。因此不用額外多跑一次確認戰鬥完的最後一個元素是否真的為主要元素。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。