力扣(leetcode) 169. 多数元素(哈希表法)（中点法) (摩尔投票法)

题目分析：

之前做过一道相似的题：​​题目在这​​​ 本次的这道题是之前那道题的简化版。

之前的题所找的多数元素不一定是主要元素，也就是不一定大于 n/2，且所给数组可能为空。

而本次所给的题，则一定存在主要元素，且数组不为空。

法一(哈希表法)：

思路分析：

使用哈希表来存储元素以及该元素出现过的次数。

最后遍历哈希表，看看那一个value大于数组长度的一般，输出该value对应的key的值。

完整代码

def majorityElement(self, nums: List[int]) -> int:
        
 
        hashmap = {}

        for i in nums: # key存值 val存出现的次数
            if i in hashmap:
                hashmap[i] +=1
            else:
                hashmap[i] = 1
        temp = 0

        for j in hashmap:

            if temp < hashmap[j]:
                temp = hashmap[j]
                ans = j

        return      

法二(中点法)：

思路分析:

仔细研究题目之后发现，如果该数组里存在 “多数元素” ，那么当数组排序后。中间的那个数必定是“多数元素”。

所以我们可以将数组排序，然后找到最中间的那个数即可。

完整代码

def majorityElement(self, nums: List[int]) -> int:
      nums.sort()
      mid = nums[len(nums) // 2]
      return      

以上两种方法均可通过leetcode，但均不符合题目要求。

一定要看清题目，题目中要求​​

​请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。​

​​ 法1中的哈希表，空间复杂度为O(n) 超出。

法2中的sort()方法，时间复杂度为O(nlogn)超出。

法三(摩尔投票法):

思路分析：

使用摩尔投票法，我们设置一个count变量。 然后遍历数组。出现相同元素的时候 count 加1，出现不同元素的时候 count减1。

如果遍历到最后 count的值 >0 则说明可能存在 “主要元素”。并不一定，因为该元素的出现次数不一定大于数组长度的一半。

设置一个res，用于记录可能的答案。

几个注意的点：

当投票计数器count = 0 的时候是什么情况？

1. 显然是一开始刚进入循环的时候。比如数组 [a,a,b]

   循环开始，刚进入数组，count = 0 则记录当前的值 res=a

2. 另外一种情况，比如数组 [a,b,b] 一开始为0 。开始遍历。

   遇到a 加1，遇到b减一。此时count为0.

   则记录当前的值 res=b

所以我们得到结论，当遍历未完成的时候出现投票计数器count = 0 时。则当前可能是答案，把他记录在res里。

有小伙伴问:那后面出现的新的res会将前面的可能答案覆盖掉啊。

这里完全不用担心这个情况，因为如果出现了新的res，则说明count为0了

肯定是出现了一个新的元素，该元素出现次数为最多，才会导致count又变成0了。

比如数组 [a,a,b,c,c,c]

显然一开始的res记录为a 。

count的变化：

遇到a 变为1

遇到a变为2

遇到b变为1

遇到c变为0 （此时记录C到res中）

遇到c变为1

遇到c变为2

最后count为2 且res记录的出现次数最多的那个值c。

所以当count = 0 。res被覆盖掉时，则说明已经有了出现次数更多的元素。

且无论数组是否有序，上面的步骤都一样，可手动模拟一下。

def majorityElement(self, nums: List[int]) -> int:        
        res = -1
        count = 0
        for i in nums:
            if count == 0:
                res = i
                count +=1
            elif res == i:
                count +=1
            else:
                count -=1
        print(res)
        return