169. Majority Element

今天我們一起挑戰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

今天的題目比較單純，這題是希望我們把題目給我們的一個整數陣列中，找到某個數是出現最多次的，並回傳那個數。而且題目保證出現最多次數的數會出現超過陣列長度的一半。

HahsMap

這題也能透過HashMap的手法，以key存放數字，value存放數字出現個數，加上比對每個數字出現個數，如果超過陣列長度的一半，就回傳該數字，以此來達成題目的要求。

以下是python的程式碼

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dit = {}
        for i in nums:  # 數字:出現個數
            if i not in dit:
                dit[i] = 1
            else:
                dit[i] += 1
        length = len(nums)
        for i in dit:  # 走訪字典，逐一檢查
            if dit[i] > (length) * 0.5:
                return i

以下是C++的程式碼，與上面解法不同是，在這段程式碼中，在建立字典的同時就持續檢查，因此不需要在完成後再走訪一次HashMap。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> dit;
        for(int num:nums){
            if(++dit[num] > nums.size() / 2)  #建立加上檢查
                return num;
        }
    return 0;
    }
};

參考資料

https://leetcode.com/problems/majority-element/discuss/51612/C%2B%2B-6-Solutions