每日一题-13

题目描述

多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

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

示例 1:

输入: [3,2,3]
输出: 3
示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

解题思路

1.利用python字典（java就是hashmap）。线性查找一次数组，以元素为键，出现的次数为值，存入字典中。当某一个元素的出现次数大于len(n)//2，这个元素即多数元素（本题多数元素唯一，所以直接返回）。

2.对数组进行排序。当这个数组为有序数组的时候，由于众数元素的个数是大于len(n)//2的，所以排序之后，直接返回数组的第len(n)//2个元素，即多数元素。

3.投票法。初始阶段，令第一元素为候选人，票数为0；然后进行判断是否与num相等，相等的num会给候选人投+1，不相等的投-1，当count（票数）等于0，换当前元素为新的候选人，然后继续投票。
最后剩下的候选人即为多数元素。这是因为多数元素的次数大于len(n)//2，所以经过+1和-1抵消投票，最后count>0的那位候选人就是多数元素。

4.力扣官方还有随机法和分治法，有兴趣的下方链接查看。
https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/

代码

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # dictData = {}
        # for num in nums:
        #     dictData[num] = dictData.get(num, 0) + 1
        #     if dictData[num] > len(nums)//2:
        #         return num

        # nums.sort()
        # return nums[len(nums)//2]

        count = 0
        candidate = float("inf") #初始时，候选人不存在
        for num in nums:
            if count == 0:#换新候选人
                candidate = num
            count += (1 if num==candidate else -1) #和自己一样，投正票，不一样投负票

        return candidate #多数元素的候选人一定会胜利