Q169 Majority Element
Q169 Majority Element
echobingo
发布于 2018-04-25 16:58:30
发布于 2018-04-25 16:58:30
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
解题思路：
将每个元素出现的次数用 Map 保存起来，返回出现次数最多的元素。
时间复杂度：O(n)；空间复杂度：O(n)
Python实现：
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = {}
maxE = maxV = 0
for val in nums: # 统计每个元素的个数
if count.get(val):
count[val] += 1
else:
count[val] = 1
for key, val in count.items():
if val > maxV:
maxE, maxV = key, val
return maxE
a = [3,2,3,3]
b = Solution()
print(b.majorityElement(a)) # 3补充：
- 一行Python代码实现，不过时间复杂度比较高：
return sorted(nums)[len(nums)/2]- 空间复杂度为 O(1) 的完美算法（火拼算法，势力相等则抵消）：
public class Solution {
public int majorityElement(int[] num) {
int major=num[0], count = 1;
for(int i=1; i<num.length;i++){
if(count==0){
count++;
major=num[i];
}else if(major==num[i]){
count++;
}else count--;
}
return major;
}
}方法2完美地抓住了列表中元素超过 n/2 次的条件，只不过我想不到。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.02.28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录