Leetcode 169. Majority Element

Majority Elementg是給定一個長度為n的陣列,返回它的majority element(出現>n/2次的值)。假設陣列不為空，且給定的陣列中一定存在majority element。

Python

方法一 : Hashmap

class Solution:
    def majorityElement(self, nums: List[int]) -> int
        init= dict()   #創一個dictionary
       
        for n in nums:
            init[n] = init.get(n, 0) + 1  #記數

            if init[n] > len(nums)//2:  #出現>n/2次的值
                return n

方法二：sort 排序法

對陣列進行排序，因為majority element一定會存在，且個數超過總個數的一半，那麼排序後最中間的那個元素一定是majority element

class Solution(object):
    def majorityElement(self, nums):

        nums.sort()
        return nums[len(nums)//2]

方法三 : Moore voting algorithm

若遇到和紀錄值一樣的值計數器+1,不一樣的值計數器-1，當計數器為0時,紀錄值轉為此時遇到的新值，若有個元素佔了陣列一半以上,最後的紀錄值便是該元素，讓各不同元素相互抵消最後只留下majority element

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

C++

定義一個計數器 count 和一個候選眾數 candidate。我們遍歷數組中的每個數，如果計數器為 0，則將當前數設置為候選眾數；否則，如果當前數等於候選眾數，則計數器加 1，否則計數器減 1。遍歷完數組後，候選眾數就是最終的答案。

時間複雜度：O(n)，其中 n 是數組的長度。

空間複雜度：O(1)。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int candidate = 0;
        
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        
        return candidate;
    }
};

Python

C++

相關