?

前言：

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

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

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

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

解法一：哈希表

動(dòng)畫演示：

代碼如下：

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

時(shí)間復(fù)雜度：O(n) ；空間復(fù)雜度：O(n)
?

解法二：排序

代碼如下：

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

時(shí)間復(fù)雜度：O(nlogn)；空間復(fù)雜度：O(nlogn)
?

解法三：分治

動(dòng)畫演示：

代碼如下：
?

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

時(shí)間復(fù)雜度：O(nlogn)? ?；空間復(fù)雜度：O(nlogn)

?

解法4：Boyer- Moore算法

思想：我們把眾數(shù)記為 +1，把其他數(shù)記為? -1，將它們?nèi)考悠饋?#xff0c;顯然和大于 0。從結(jié)果本身，我們可以看出，眾數(shù)比其他數(shù)多。

?

代碼如下：

?

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

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

時(shí)間復(fù)雜度：O(n)；空間復(fù)雜度：O(1)
?

絮叨

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

---

專注后臺(tái)開發(fā)相關(guān)技術(shù)，廣度深度并存，干貨情懷同在。
微信搜索【盼盼編程】關(guān)注這個(gè)不一樣的程序員。

總結(jié)

以上是生活随笔為你收集整理的算法：多数元素，多种解法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。