【LeetCode】 169. Majority Element

Description

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

給一個大小為n的陣列，請找到它的主要元素。主要元素指它出現的次數大於 ⌊ n/2 ⌋ 次的元素。

你可以假設陣列不會是空的，且主要元素總是存在於陣列中。

Example:

Example 1:

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


Example 2:

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

Solution

• 方法一：hash table去存元素出現的次數，較節省時間。
• 方法二：先排序，再直接回傳陣列最中間的數，較節省空間。

Code

• 方法一：

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

• 方法二：

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

tags: LeetCode C++