问题描述
解法 1
分析
Python 实现
1 2 3 4 5 6 7 8 9 10
|
class : def majorityElement(self, nums): """ :type nums: List[int] :rtype: int """ counter = dict() for n in nums: counter[n] = counter.get(n, 0) + 1 return max(counter.keys(), key=lambda n : counter.get(n))
|
Java 实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
|
class { public int majorityElement(int[] nums) { Map<Integer, Integer> counter = new HashMap<>(); for(int n : nums){ counter.put(n, counter.getOrDefault(n,0)+1); } int ans = 0; int maxFreq = 0; for(Map.Entry<Integer, Integer> entry : counter.entrySet()){ int n = entry.getKey(); int freq = entry.getValue(); if(freq > maxFreq){ ans = n; maxFreq = freq; } } return ans; } }
|
时间复杂度
O(n).
空间复杂度
O(n).
解法 2
分析
Python 实现
1 2 3 4 5 6 7
|
class (object): def majorityElement(self, nums): """ :type nums: List[int] :rtype: int """ return sorted(nums)[len(nums)//2]
|
Java 实现
1 2 3 4 5 6
|
class { public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; } }
|
时间复杂度
O(nlogn).
空间复杂度
O(1).
链接
169. Majority Element
169. 求众数
(English version) Algorithm Notes: Leetcode#169 Majority Element
近期评论