Majority Element

投票算法的简单版，因为题目里面确保有解，我们可以只进行主要逻辑部分就行了，如果不一定有解，我们还必须把candidate再循环检查一遍是不是正确

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = nums[0]
        count = 1
        n = len(nums)

        for i in xrange(1, n):
            if nums[i] != result:
                count -= 1
                if count <= 0:
                    count = 1
                    result = nums[i]
            else:
                count += 1

        return result

这题还可以利用和single number差不多的思路，即强行枚举所有比特位进行统计，因为Python没有限制的原因，最后结果处理很麻烦，这里用Java代码了解思路即可

public class Solution {
    public int majorityElement(int[] nums) {
        int base = 0;
        int result = 0;

        for (int i = 0; i <= 31; ++i) {
            base = 1 << i;
            int count = 0;
            for (int num : nums) {
                if ((num & base) != 0) {
                    count++;
                }
            }

            if (count > nums.length / 2) {
                result |= base;
            }
        }

        return result;
    }
}

Majority Element II

第二题其实就可以算作投票算法的泛化了，之前瞎堆逻辑做出来的根本没有参考价值，这种类似的题一定要有一个通用模板才能理解并应用

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n, m = 0, 0
        countN, countM = 0, 0
        for num in nums:
            if n == num:
                countN += 1
            elif m == num:
                countM += 1
            elif countN == 0:
                n = num
                countN = 1
            elif countM == 0:
                m = num
                countM = 1
            else:
                countN -= 1
                countM -= 1

        countN, countM = 0, 0
        for num in nums:
            if n == num:
                countN += 1
            elif m == num:
                countM += 1

        result = []
        if countN > len(nums) / 3:
            result.append(n)
        if countM > len(nums) / 3:
            result.append(m)
        return result

参考：http://www.cnblogs.com/grandyang/p/4606822.html