题目描述

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, 1, 2, 3, 4, 5, 1, 1, 2, 1, 1]有：

1   2
1   3
1   4
1   5
1   2
------
1

所以如果我们总能将两个不同元素从数组中拿出来配对，那么如此循环最后剩下的不能配对的元素（即剩下的都是相同元素）就是占大多数的元素。

注意上面说两个不同元素并没有说其中一个元素一定要是占大多数的元素，因为如果两个不同元素均不是占大多数的元素，那得到结果会更快，还是以[1, 1, 2, 3, 4, 5, 1, 1, 2, 1, 1]为例，来看看配对的过程：

i = 0           count_1 = 0 -> 1
i = 1           count_1 = 1 -> 2
i = 2   1   2   count_1 = 2 -> 1
i = 3   1   3   count_1 = 1 -> 0
i = 4           count_1 = 0
i = 5   4   5   count_1 = 0
i = 6           count_1 = 0 -> 1
i = 7           count_1 = 0 -> 2
i = 8   1   2   count_1 = 2 -> 1
i = 9           count_1 = 1 -> 2
i = 10          count_1 = 2 -> 3

output: 1

对于代码实现来说也很简单，维持一个majority变量记录当前认为的占大多数的元素，维持一个count变量记录还未配对的majority的数量；遍历数组，一旦碰到count = 0，就将当前的元素认为majority；再然后检查当前元素与majority是否相等，如果相等就记录count加一，如果不相等就记录count减一（配对成功）。

Python

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        majority = None
        count = 0
        for num in nums:
            if count == 0:
                majority = num
            if majority == num:
                count += 1
            else:
                count -= 1
        return majority

Java

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

C++

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