LeetCode #169 #229 2018-08-07

169. Majority Element

https://leetcode.com/problems/majority-element/description/

又到了一年一度的Majority Number选举，每个数字都为自己投票，Majority Number获得的票数最多。不同的数字会抵消Majority Number的投票。
代码如下：

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

229. Majority Element II

https://leetcode.com/problems/majority-element-ii/description/

使用2个候选变量储存结果即可。注意，第一遍的count1和count2并不是2个候选数字在数组中出现的次数，需要重新扫描一遍数组，找出最终结果。
代码如下：

class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums:
            return []
        result = []
        value1, value2, count1, count2 = nums[0], 0, 1, 0
        for i in range(1, len(nums)):
            if nums[i] == value1:
                count1 += 1
            elif nums[i] == value2:
                count2 += 1
            elif count1 == 0:
                value1, count1 = nums[i], 1
            elif count2 == 0:
                value2, count2 = nums[i], 1
            else:
                count1 -= 1
                count2 -= 1
        return list(set([num for num in (value1, value2) if nums.count(num) > len(nums) // 3]))