LeetCode 169. 多數元素【c++/java詳細題解】

1、題目

給定一個大小為 n 的陣列，找到其中的多數元素，多數元素是指在陣列中出現次數 大于 ? n/2 ? 的元素，

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

示例 1：

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

示例 2：

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

進階：

• 嘗試設計時間復雜度為 O ( n ) O(n) O(n)、空間復雜度為 O ( 1 ) O(1) O(1) 的演算法解決此問題，

2、思路1

(哈希表) O ( n ) O(n) O(n)

1、使用用哈希表記錄每個元素出現多少次，

2、判斷每個元素出現的次數是否大于 n / 2 n/2 n/2，如果大于，則回傳該數字即可，

時間復雜度分析： O ( n ) O(n) O(n)

空間復雜度分析： 至少需要額外的 O ( n ) O(n) O(n) 空間，

3、c++代碼1

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) 
        {
            hash[nums[i]] += 1;
            if (hash[nums[i]] > nums.size() / 2)

                return nums[i];
        }
        return 0;
    }
};

4、java代碼1

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int n = nums.length;
        for(int i = 0;i < n;i ++) 
        {
            int x = nums[i];
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        int res = 0;
        int count = 0;
        for(Map.Entry<Integer, Integer> entry : map.entrySet())
        {
            if(entry.getValue() > count)
            {
                count = entry.getValue();
                res = entry.getKey();
            }
        }
        return res;
    }
}

5、思路2

(投票演算法) O ( n ) O(n) O(n)

當一個國家的總統候選人r的支持率大于50%的話，即使每個反對他的人都給他投一個反對票，抵消掉他的支持票，他的支持票也不會被完全消耗掉，因此，我們可以假定和r相同的數都是支持票，和r不同的數都是反對票，

維護兩個變數：候選人和他的票數

• 1、候選人初始化為r = 0，票數c初始化為0，遍歷整個陣列
• 2、當候選人的票數為0時，更換候選人，并將票數重置為1
• 3、當候選人的值和當前元素相同時，票數加1，否則減1
• 4、最后維護的候選人即是答案

時間復雜度分析： O ( n ) O(n) O(n) ， n n n是陣列的大小，

空間復雜度分析： 僅使用了兩個變數，故需要 O ( 1 ) O(1) O(1) 的額外空間，

6、c++代碼2

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int r, c = 0;
        for (auto x: nums)
            if (!c) r = x, c = 1;   //重置候選人
            else if (r == x) c ++ ; //票數加一
            else c -- ;  //票數減一
        return r;
    }
};

7、Java代碼2

class Solution {
    public int majorityElement(int[] nums) {
        int r = 0,c = 0;
        for(int i = 0;i < nums.length;i ++)
        {
            int x = nums[i];
            if(c == 0) { r = x; c = 1; } //重置候選人
            else if(r == x) c ++; //票數加一
            else c --;  //票數減一
        }
        return r;
    }
}

原題鏈接： 169. 多數元素