(day31)leecode热题——多数元素

描述

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

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

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 104
• -109 <= nums[i] <= 109

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

 小垃圾代码

from collections import Counter
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dic = Counter(nums)
        tar = max(dic.values())
        for key,val in dic.items():
            if val == tar:
                return key

 leecode题解 ̶.̶G̶F̶u̶＇̶ 、̶ ̶|

排序思路

既然数组中有出现次数 > ⌊ n/2 ⌋ 的元素，那排好序之后的数组中，相同元素 总是 相邻 的。
即存在长度 > ⌊ n/2 ⌋ 的一长串 由 相同元素 构成的 连续子数组。
举个例子：
无论是 1 1 1 2 3，0 1 1 1 2 还是 -1 0 1 1 1，数组中间的元素总是“多数元素”，毕竟它长度 > ⌊ n/2 ⌋。

代码 

class Solution:
    def majorityElement(self, nums):
        # 对列表进行排序
        nums.sort()
        
        # 返回排序后位于中间位置的元素
        return nums[len(nums) // 2]

整体分析

这个函数的目标是找到一个数组中出现次数超过数组长度一半的“主要元素”。在这个实现中，首先将数组排序，之后直接返回排序后位于数组中间的元素。

这种方法利用了排序的特点，主要元素在排序后会出现在数组的中间位置。排序的时间复杂度是O(n log n)，而返回中间元素的操作是O(1)，因此整体的时间复杂度是O(n log n)，空间复杂度为O(1)（假设排序是原地排序的）。

这种方法虽然效率稍低于线性时间的解法，但实现起来非常简单且直观，非常适合用于多数元素问题的解决。

进阶（时间 O(n), 空间O(1)）

摩尔投票法思路

候选人(cand_num)初始化为 nums[0]，票数 count 初始化为 1。
当遇到与 cand_num 相同的数，则票数 count = count + 1，否则票数 count = count - 1。
当票数 count 为 0 时，更换候选人，并将票数 count 重置为 1。
遍历完数组后，cand_num 即为最终答案。

为何这行得通呢？
投票法是遇到相同的则 票数 + 1，遇到不同的则 票数 - 1。
且“多数元素”的个数 > ⌊ n/2 ⌋，其余元素的个数总和 <= ⌊ n/2 ⌋。
因此“多数元素”的个数 - 其余元素的个数总和 的结果 肯定 >= 1。
这就相当于每个 “多数元素” 和其他元素 两两相互抵消，抵消到最后肯定还剩余 至少1个 “多数元素”。

无论数组是 1 2 1 2 1，亦或是 1 2 2 1 1，总能得到正确的候选人。

 代码

class Solution:
    def majorityElement(self, nums):
        # 初始化候选多数元素为数组的第一个元素，计数器为1
        cand_num = nums[0]
        count = 1
        
        # 从第二个元素开始遍历数组
        for i in range(1, len(nums)):
            if cand_num == nums[i]:
                # 如果当前元素等于候选元素，则计数器加1
                count += 1
            else:
                # 如果当前元素不等于候选元素，计数器减1
                count -= 1
                
                # 当计数器减为0时，更新候选元素为当前元素，并将计数器重置为1
                if count == 0:
                    cand_num = nums[i]
                    count = 1
        
        # 返回最终确定的候选元素
        return cand_num

整体分析

这个算法基于 Boyer-Moore 投票算法，用于寻找数组中的多数元素（即出现次数超过一半的元素）。算法的基本思想是：通过在数组中持续选取候选元素并统计其支持度，当支持度降为零时更换候选元素，最终剩下的候选元素即为数组的多数元素。

• 时间复杂度：O(n)，因为我们只需要遍历数组一次。
• 空间复杂度：O(1)，因为除了几个额外的变量之外，算法不需要额外的存储空间。

这种方法非常高效且简洁，在求解多数元素问题时具有广泛的应用。