北京
在算法面試中，尋找數(shù)組中的多數(shù)元素是一道經(jīng)典題目。LeetCode第169題要求從給定數(shù)組中找出出現(xiàn)次數(shù)超過?n/2?的元素，題目保證這樣的元素一定存在。面對這道題，絕大多數(shù)人首先會想到用哈希表統(tǒng)計頻率，但還有另一種更節(jié)省空間的摩爾投票算法，只需常數(shù)級額外空間即可快速鎖定答案。本文將深入對比這兩種解法的優(yōu)劣，幫助你從容應對面試官的追問。
以數(shù)組 nums = [2,4,2,2,4,4,4] 為例，多數(shù)元素為4，因為它出現(xiàn)了4次，超過長度7的一半。方法一：頻率哈希表。創(chuàng)建一個 Map，遍歷數(shù)組，用每個值作為鍵，出現(xiàn)次數(shù)作為值。對每個元素，如果 Map 中已存在，則計數(shù)加1，否則初始化為1。隨后再次遍歷 Map，一旦發(fā)現(xiàn)某個計數(shù)大于 n/2，直接返回該元素。代碼如下：
function majorityElement(nums) { const counts = new Map(); for (const num of nums) { counts.set(num, (counts.get(num) ?? 0) + 1); } for (const [num, count] of counts) { if (count > nums.length / 2) return num; } }
該方法時間復雜度 O(n)，但空間復雜度也為 O(n)，因為哈希表最多存儲 n 個不同元素。在數(shù)據(jù)量極大時，內(nèi)存消耗會成為瓶頸。此時，Boyer-Moore 摩爾投票算法展現(xiàn)出巨大優(yōu)勢。它基于一個核心洞察：如果把多數(shù)元素和其他元素兩兩抵消，最后剩下的一定是多數(shù)元素。算法維護一個候選值和一個計數(shù)器，遍歷數(shù)組時，若計數(shù)器為0則將當前元素設(shè)為候選值，隨后如果當前元素與候選值相同則計數(shù)器加1，否則減1。遍歷結(jié)束后，候選值就是多數(shù)元素。整個過程只用了兩個變量，空間復雜度 O(1)，時間復雜度仍然 O(n)。
對比兩種方法，哈希表簡單直觀，適合快速實現(xiàn)；摩爾投票算法則更高效，能體現(xiàn)對問題本質(zhì)的深刻理解。在面試中，如果能從哈希表平滑過渡到摩爾投票算法，并解釋其正確性，往往會給面試官留下深刻印象。LeetCode 169雖簡單，卻蘊含著優(yōu)化思維的寶貴訓練價值。
特別聲明：以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺“網(wǎng)易號”用戶上傳并發(fā)布，本平臺僅提供信息存儲服務。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
