騰訊二面：多數元素

前言:

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

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

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

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

解法一：哈希表

動畫演示：

代碼如下：

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

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

解法二：排序

代碼如下：

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

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

解法三：分治

動畫演示：

代碼如下：

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

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

解法4：Boyer- Moore算法

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

代碼如下：

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

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

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

絮叨

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