LeetCode求眾數(尋找多數元素/主元素問題)

收藏待读

LeetCode求眾數(尋找多數元素/主元素問題)

1、題目描述

給定一個大小為 n 的數組,找到其中的眾數。眾數是指在數組中出現次數大於 ⌊ n/2 ⌋ 的元素。

你可以假設數組是非空的,並且給定的數組總是存在眾數。

示例 1:

輸入: [3,2,3]
輸出: 3

示例 2:

輸入: [2,2,1,1,1,2,2]
輸出: 2

說明:

此題也叫做 尋找多數元素/主元素問題 。解決這個問題有好多種方法,蠻力方法就是把序列中的每個元素和其他每個元素比較,並且對每個元素計數,如果某個元素的計數大於n/2,就可以判斷它是多數元素,否則無多數元素。但是這樣的比較次數是n(n-1)/2=O(n^2),複雜度高。比較有效的算法是先對這些元素排序,並且計算每個元素在序列中出現的次數,最壞情況下是O(nlogn)。因為排序這一步需要O(nlogn)次比較,也相對比較高,是不符合時間上的要求的,因此就有了一種相比之下更聰明的方法。

2、解法:

在原序列中去除兩個不同的元素以後,原序列中的多數元素在新的序列中還是多數元素

說明

採用count來標記主元素的個數,假設第一個是主元素,從第二個開始比對,如果相等,則count++,否則,則是count–,當count減到0的時候,主元素默認為下一個。 count加減的過程中,就是在模擬去掉兩個不同元素的過程!

代碼如下:

public int majorityElement(int[] nums) {
        int count = 1;
        int maj = nums[0];
        for (int i = 1; i 
    

經測試,可行!

附上leetcode此題鏈接:

https://leetcode-cn.com/problems/majority-element/

原文 : 簡書

相關閱讀

免责声明:本文内容来源于簡書,已注明原文出处和链接,文章观点不代表立场,如若侵犯到您的权益,或涉不实谣言,敬请向我们提出检举。