LeetCode-169-多数元素

2020-12-05  本文已影响0人  阿凯被注册了

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于n/2的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。


image.png

解题思路:

  1. 字典存储出现次数;
  2. 排序后求众数;
  3. 遍历一次,不等就消除,相等则累计。

Python3代码:

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        ans = {}
        n = len(nums)
        if n==1:
            return nums[0]
        for i in range(n):
            if nums[i] not in ans:
                ans[nums[i]]=1
            else:
                ans[nums[i]]+=1
                if ans[nums[i]]>n//2:
                    return nums[i]
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums) // 2]
class Solution: 
    def majorityElement(self, nums: List[int]) -> int:
        ans = nums[0]
        len1 = 1
        for i in range(1, len(nums)):
            if nums[i] == ans: # 相等说明重复两个数字
               len1+=1
            else: # 不等
                if len1 > 0:  # 消除
                    len1-=1 
                else:
                    ans=nums[i]
                    len1 = 1
        return ans
上一篇 下一篇

猜你喜欢

热点阅读