專注后臺開發相關技術，廣度深度并存，干貨情懷同在，
微信搜索【晨夢思雨】關注這個不一樣的程式員，

??強烈推薦人工智能學習網站??

前言：

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

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

題目：
給定一個大小為 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)

絮叨

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