0.前言

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.

1.c++版本

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        if (nums.empty())
            return 0;
        int n = nums.size()/2;
        sort(nums.begin(), nums.end());
        int count = 0, i = 0;
        for (; i< nums.size()-1; ++i) {
            if (nums[i] == nums[i+1]) {
                count++;
                if (count >= n)
                    return nums[i];
            }
            else
                count = 0;
        }
        if (i==0)
            return nums[i];
        return 0;
    }
};

方法2：使用hashtable

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counter;
        for (int num : nums) {
            if (++counter[num] > nums.size() / 2) {
                return num;
            }
        }
        return 0;
    }
};

方式3. Sorting. Since the majority element appears more than n / 2 times, the n / 2-th element in the sorted nums must be the majority element. In this case, a partial sort by nth_element is enough.

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

2. python版本

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        length = len(nums)/2
        nums.sort()
        count = 0
        for i in range(0, len(nums)-1):
            if nums[i] == nums[i+1]:
                count += 1
                if count >= length:
                    return nums[i]
            else:
                 count = 0
        if length == 0:
            return nums[0]
        return 0