數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字。

你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。

示例

• 輸入: [1, 2, 3, 2, 2, 2, 5, 4, 2]

• 輸出: 2

限制

• 1 <= 數(shù)組長度 <= 50000

方法：哈希表

我們創(chuàng)建一個哈希表用來統(tǒng)計每個元素出現(xiàn)的次數(shù)，當循環(huán)遍歷數(shù)組的時候，如果當前元素出現(xiàn)的次數(shù)大于目標數(shù)組的長度的一半，立即返回該元素即可。

代碼如下：

復(fù)雜度分析

• 時間復(fù)雜度：O(n)，其中 n 是數(shù)組 nums 的長度。

• 空間復(fù)雜度：O(n)。

方法：數(shù)組排序

如果將數(shù)組中所有元素進行順序排序，那么數(shù)組中間的元素一定是眾數(shù)。

代碼如下：

復(fù)雜度分析

• 時間復(fù)雜度：O(nlogn)。將數(shù)組排序的時間復(fù)雜度為 O(nlogn)。

• 空間復(fù)雜度：O(logn)。

方法：摩爾投票法

Boyer-Moore majority vote algorithm，該算法解決的問題是如何在任意多的候選人（選票無序），選出獲得票數(shù)最多的那位。

• 維護一個眾數(shù)和他出現(xiàn)的次數(shù)。

• 遍歷數(shù)組中的所有元素，如果次數(shù)為 0，我們就把眾數(shù)賦值為當前值。

• 如果眾數(shù)等于當前值，次數(shù)加 1；否則減 1；

• 遍歷完整個數(shù)組后，最后統(tǒng)計的眾數(shù)即為整個數(shù)組的眾數(shù)。

代碼如下：

復(fù)雜度分析

• 時間復(fù)雜度：O(n)。Boyer-Moore 算法只對數(shù)組進行了一次遍歷。

• 空間復(fù)雜度：O(1)。Boyer-Moore 算法只需要常數(shù)級別的額外空間。

END

水滴集多成大海，讀書集多成學問，贈友人。

好兄弟可以點贊并關(guān)注我的公眾號“javaAnswer”，全部都是干貨。