騰訊二面：多數(shù)元素

前言:

以前做數(shù)學題的時候，老師說：你們學習多種解題方法。遇到類似不同的問題，你都會了，這樣能提高解題能力。如果你寫出多種解法，面試官會對你刮目相看。

下面一題，我們將用多種解法實現(xiàn)，是面試中常見的一題。

題目：
給定一個大小為 n 的數(shù)組，找到其中的多數(shù)元素。多數(shù)元素是指，在數(shù)組中出現(xiàn)次數(shù)，大于? n / 2 的元素。
例子：int a[3] =? {1, 2, 2} ，多數(shù)元素是 2 。?

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

解法一：哈希表

動畫演示：

代碼如下：

哈希表方法：一邊遍歷，一邊計數(shù)，一邊找眾數(shù)，并不是先計數(shù)完，再去遍歷一次找最大值。

時間復雜度：O(n) ；空間復雜度：O(n)

解法二：排序

代碼如下：

對數(shù)組排序后，直接可以通過下標來判斷眾數(shù)，這個方法簡單。

時間復雜度：O(nlogn)；空間復雜度：O(nlogn)

解法三：分治

動畫演示：

代碼如下：

先將數(shù)組劃分，然后分別找到左邊的眾數(shù)和右邊的眾數(shù)，然后根據(jù)找到的眾數(shù)和數(shù)組長度的 1 / 2 進行比較。

時間復雜度：O(nlogn)? ?；空間復雜度：O(nlogn)

解法4：Boyer- Moore算法

思想：我們把眾數(shù)記為 +1，把其他數(shù)記為? -1，將它們全部加起來，顯然和大于 0。從結果本身，我們可以看出，眾數(shù)比其他數(shù)多。

代碼如下：

遍歷數(shù)組 nums 中的所有元素，對于每個元素 x，在判斷 x 之前，如果 count 的值為 0，先將 x 的值賦予 more，隨后我們判斷 x：

????如果 x 與 more相等，那么計數(shù)器 count 的值增加 1；
????如果 x 與 more不等，那么計數(shù)器 count 的值減少 1。

時間復雜度：O(n)；空間復雜度：O(1)

絮叨

面試過程中，選擇你熟悉的算法中，時間和空間復雜度最優(yōu)的解法，平時訓練多種方法都要懂，提高算法能力。