02_多数元素(Python)

布满荆棘的人生 2023-01-13 05:52 100阅读 0赞

### 目录 ###

*  多数元素
 *  示例 1：
 *  示例 2：
 *  进阶：
 *  解答
 *   *  1，先排序
     *  2，使用Map解决
     *  3，位运算解决
     *  4，摩尔投票法

# 多数元素 #

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

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

# 示例 1： #

> 输入：\[3,2,3\]  
> 输出：3

# 示例 2： #

> 输入：\[2,2,1,1,1,2,2\]  
> 输出：2

# 进阶： #

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

# 解答 #

## 1，先排序 ##

题中说了给定的数组总是存在多数元素，也就是说肯定有一个元素的个数大于数组长度的一半。我们只需要把这个数组排序，那么数组中间的值肯定是存在最多的元素。

其实很容易证明，假设排序之后数组的中间值不是最多的元素，那么这个最多的元素要么是在数组前半部分，要么是在数组的后半部分，无论在哪，他的长度都不可能超过数组长度的一半。

> 列表排序:
> 
>     list.sort(cmp=None, key=None, reverse=False)
> 
> 该方法没有返回值，但是会对列表的对象进行排序。

class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            # 排序后输出中位数
            nums.sort()
            return nums[len(nums)//2]

## 2，使用Map解决 ##

还可以使用Map来解决，map的key存放的是数组中的元素，value是数组中元素的个数，把数组中元素不断的存放到map中，如果某个元素的个数大于数组长度的一半，直接返回。

class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            # 使用Map解决
            dict = { }
            for i in nums:
                if i in dict:
                    dict[i]+=1
                    if dict[i]>len(nums)//2:
                        return i
                else:
                    dict[i]=1
            return nums[0]

## 3，位运算解决 ##

在java中int类型是32位的，我们只需要判断所有数字在某一位1的个数大于数组长度的一半，那么这个众数在这个位置肯定就是1，我们需要遍历32次，确定这个众数每个位置是0还是1即可。

哎? 在python中可不是这样!!!

好麻烦呀 - - - - - - 这个不写了md

## 4，摩尔投票法 ##

假设数组中每个不同的数字就代表一个国家，而数字的个数就代表这个国家的人数，他们在一起混战，就是每两个两个同归于尽。我们就可以知道那个人数大于数组长度一半的肯定会获胜。

就算退一万步来说，其他的所有人都来攻击这个人数最多的国家，他们每两个两个同归于尽，最终剩下的也是那个众数。

class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            vote= 0
            res = 0
            for num in nums:
                if vote==0:
                    res = num            
                vote = vote + 1 if res==num else vote - 1 
            return res