Q169 Majority Element

echobingo

发布于 2018-04-25 16:58:30

8840

发布于 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 删除

python