Leetcode 229. Majority Element II 题解
题目
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋
times.
Note: The algorithm should run in linear time and in O(1) space.
Example 1:
Input: [3,2,3]
Output: [3]
Example 2:
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
分析
首先可以知道对于题目中的这种情况,如果存在这样的一种最多出现次数的数字,也就是 appear more than ⌊ n/3 ⌋
times 的话,这样的数字最多有两个,这里简单说明一下为什么最多只会有两个。
对于一个长度为n的数组,n是整数,那么我们可以使用 $3k, 3k+1,3k+2$ ,k是整数来表示一个n,这三种情况下最后计算得到要求的答案数字个数要大于k,也就是最小要是$k+1$,如果一个数组里面有三个这样的数字的话,3个$k+1$,将大于最大的$3k+2$,不符合要求所以最多有2个答案。
确定了最多有两个数字之后,这道题可以使用字典计数来确定,但是题目要求要用一个线性时间的算法,而且需要一个$O(1)$ 的空间复杂度,这就需要用 majority vote 算法,多数投票法。
显然,如果一个数字满足大多数这个条件的话,相当于对其投票,相同的数字就在其的count上面加1,不相同的就减一,如果这个候选人的票被减没了,那么就会有新的参选者加入,在这个题目中,我们设置两个候选人,如果遇到相同的情况就对对应的count加一,当count=0的时候更换候选人,如果count没有减到0,那么就减1,这样我们就可以找到最后的两个人,也就是两个数字。
但是这里面是有一些问题的,首先的确能找到两个数字,不用担心过程中会出现原本很多次出现的数字被洗刷掉的情况,因为如果某个数字满足条件,在这个投票过程中,一定会成功的取代出现次数比自己小的数字,如果它的量足够,但是我们不能保证最后出来的两个数字都满足条件,多数不一定是满足⌊ n/3 ⌋,所以我们需要再进行一次遍历数组,计算到底有多少个这样的数字,最后和⌊ n/3 ⌋比较,大于这个就是真结果,小于这个就是假结果,舍去,最后得到正确的答案。
代码
from typing import List
\# ** majority vote Algo.*
def majorityElement(self, nums: List[int]) -> List[int]:
count0 = count1 = 0
target0 = target1 = 0
length = len(nums)
for x in range(length):
if nums[x] == target0:
count0 += 1
elif nums[x] == target1:
count1 += 1
elif count0 == 0:
count0 += 1
target0 = nums[x]
elif count1 == 0:
count1 += 1
target1 = nums[x]
else:
count0 -= 1
count1 -= 1
count0 = 0
count1 = 0
for x in range(length):
if nums[x] == target0:
count0 += 1
\#*!important to have a elif if!*
\#*!to avoid target0 == target1 and get two answer!*
elif nums[x] == target1:
count1 += 1
ans = []
k = length // 3
if count0 > k:
ans**.**append(target0)
if count1 > k:
ans**.**append(target1)
return ans
Python中新加入了Typing的支持,应该是学习静态语言方便查错等等的,在这里注意里面第二遍遍历中的是elif检查第二个target参选者,如果不用elif,有可能出现target0 == target1,得到结果两个数字相同的错误结果。