Skip to content

LeetCode: 169-Majority Element 解題紀錄

題目

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -231 <= nums[i] <= 231 - 1

Follow-up: Could you solve the problem in linear time and in O(1) space?

題目給定一組整數陣列的輸入，而我們要返回陣列中的多數元素（majority element）。

多數元素的定義是此元素在這陣列當中至少出現了超過一半的次數。

解題思路

這是個很好玩的題目，我一開始想出了兩種解答，但始終達成不了 Follow-up 所說的線性時間、O(1) 空間。

最後查看了他人的討論，這才發現使用 Moore voting algorithm（摩爾投票演算法）可以順利解開題目。

以下分別紀錄三種不同的解題方法。


排序法

由於多數元素一定佔超過一半長度的陣列，於是我們只需要先經過排序、再直接取陣列中間的值，就一定是多數元素。


排序法複雜度

由於使用了 quick sort，故時間複雜度一開始就是 n*log(n) 了。好處是不怎麼需要存取其他空間。

Time ComplexityO(n*log(n))
Space ComplexityO(1)


排序法 C++ 範例程式碼

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size()/2];
    }
};



排序法 Python 範例程式碼

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]




Hash map

這題也可以很暴力地使用 hash map 來記錄每個元素出現的次數，這應該是很多人想到的第一感吧！


Hash map 複雜度

因為開了 O(n) 的 map，所以空間複雜度沒有達到 follow-up 的要求。

Time ComplexityO(n)
Space ComplexityO(n)


Hash map C++ 範例程式碼

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // Init
        int major = 0;
        unordered_map<int, int> mp;
        
        // Count
        for (auto n: nums) {
            ++mp[n];
            
            if (mp[n] > nums.size()/2) {
                major = n;
                break;
            }
        }
        
        return major;
    }
};



Hash map Python 範例程式碼

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # Init
        mp = dict()
        
        # Count
        for n in nums:
            mp[n] = mp.get(n, 0) + 1
            
            if mp[n] > len(nums)//2:
                return n




Moore voting algorithm（達成要求！）

基本上，這個演算法最早似乎是用來計算哪位候選人的投票數過半的。

我們先想像一個情境，設定一個當前正在接受檢驗的候選人，只要目前統計（count）為零，就先把檢驗的候選人設定成第一位計票者，接著在每次碰到相同的候選人時，將統計數（count）加一；反之碰到不同的候選人時，將統計票數（count）減一。

當然，我們所檢驗的第一位候選人可能並不是票數過半的那位，那麼這位候選人自然而然就會碰到比自己數量還多的候選人的票，自然計票（count）就會回歸到零。當我們又遇到計票數為零的時候，我們就會開始把下一位計票的候選人當成正在檢驗的候選人，開始重複上述的過程……

那最後留下來的候選人是誰呢？沒錯，就是票數過半的候選人才會留下來。

假設我們的投票分別是 A A C C B B B A A C C C，那麼我們計票的流程如下：

  1. [A] major = A, count = 1
  2. [A] major = A, count = 2
  3. [C] major = A, count = 1
  4. [C] major = A, count = 0
  5. [B] major = B, count = 1
  6. [B] major = B, count = 2
  7. [B] major = B, count = 3
  8. [A] major = B, count = 2
  9. [A] major = B, count = 1
  10. [C] major = B, count = 0
  11. [C] major = C, count = 1
  12. [C] major = C, count = 2

最後留下的只會是票數過半的 C。


Moore voting algorithm 複雜度

而這個演算法由於只需要存取當前計算的數值（major）跟計數（count），故空間複雜度是 O(1)。

而只需要把陣列跑一遍就統計完了，故為線性時間。

Time ComplexityO(n)
Space ComplexityO(1)


Moore voting algorithm C++ 範例程式碼

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // Init
        int major = 0;
        int count = 0;
                
        // Count
        for (auto n: nums) {
            if (count == 0) major = n;

            if (major == n) ++count;
            else --count;
        }
        
        return major;
    }
};



Moore voting algorithm Python 範例程式碼

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # Init
        major = 0
        count = 0
        
        # Count
        for n in nums:
            if count == 0:
                major = n
            
            if major == n:
                count += 1
            else:
                count -= 1
        
        return major

References

Read More

Tags:

Leave a Reply