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.
Python Solution:
import collections
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
d = collections.defaultdict(int)
for num in nums:
d[num] += 1
if d[num] > len(nums) // 2:
return num
C Solution:
int majorityElement(int* nums, int numsSize) {
int major, count = 0;
int i;
for (i = 0; i < numsSize; i++) {
if (count == 0) {
major = nums[i];
count++;
}
else if (major != nums[i]) {
count--;
}
else count++;
}
return major;
}
Summary:
- Hash-Table is a classic solution, but for this problem, C solution is beautiful.
LeetCode: 169. Majority Element
近期评论