剑指 Offer 39. 数组中出现次数超过一半的数字 python

题目：

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解题思路：

方法一：字典法

利用字典，将nums的值储存为字典的key值，出现的次数储存为value值。如果key值不在字典里，则value值等于1，否则每次加一。如果value值大于数组长度的一半，返回数组的值。循环结束，其他情况则返回 0。

字典是一种可变容器模型，且可存储任意类型对象，字典格式如下

{key1 : value1, key2 : value2 }

代码：

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dict={}
        for i in nums:
            if i not in dict:
                dict[i] = 1
            else:
                dict[i] +=1
            if dict[i]>len(nums)/2:
                return i
        else:
            return 0

s = Solution()
#print(s.majorityElement([1, 2 , 3, 3, 3, 4, 3, 5, 3]))
print(s.majorityElement([3,3,4]))

运行结果

看看 性能

有点菜。

方法二

摩尔投票法

思路：有点像打擂台，遇到不是自己的就同归于尽，剩下来的那个就是下想找的那个

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


s = Solution()
# print(s.majorityElement([1, 2 , 3, 3, 3, 4, 3, 5, 3]))
print(s.majorityElement([2, 2, 3, 2, 1]))

看看结果