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

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

Credits:
Special thanks to@tsfor adding this problem and creating all test cases.

给一个大小为n的数组,找出它的多数元素。数组非空,多数元素存在。多数元素:出现次数超过n/2的元素(超过数组长度一半)。

解法1: 用两个循环跟踪统计最多次数的元素。 T:O(n*n) S: O(1)

解法2: BST,T:O(nlogn) S: O(n)

解法3:Boyer–Moore majority vote algorithm,T:O(n) S: O(1)

解法4: HashMap,T:O(n) S: O(n)

Java:

public class Solution {
    public int majorityElement(int[] nums) {
        int res = 0, cnt = 0;
        for (int num : nums) {
            if (cnt == 0) {res = num; ++cnt;}
            else if (num == res) ++cnt;
            else --cnt;
        }
        return res;
    }
}  

Python: T: O(n), S: O(1)

class Solution:
    def majorityElement(self, nums):
        idx, cnt = 0, 1
        
        for i in xrange(1, len(nums)):
            if nums[idx] == nums[i]:
                cnt += 1
            else:
                cnt -= 1
                if cnt == 0:
                    idx = i
                    cnt = 1
        
        return nums[idx]

C++:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ans = nums[0], cnt = 1;
        for (const auto& i : nums) {
            if (i == ans) {
                ++cnt;
            } else {
                --cnt;
                if (cnt == 0) {
                    ans = i;
                    cnt = 1;
                }
            }
        }
        return ans; 
    }
};

All LeetCode Questions List 题目汇总