LeetCode#169. Majority Element

LeetCode#169 Majority Element

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.

分析

这道题很简单,可以先排序,中间的数就是答案。

1
2
3
int majority(nums)  // nums is a integer array
sort(nums)
return nums[nums.length / 2]

只有想不到

1
2
3
4
5
6
7
8
9
10
11
12
int majority(nums)
target = 0;
count = 0;
for (n in nums)
if (count = 0)
target = n
count++
else if (target = n)
count++
else
count--
return target

如果我们用一个数字count记录一个数target出现的次数,如果下一个数还是这个数就将count1,否则减1。如果count0,就以下一个数为target并重新开始计算count。最后输出target。因为目标数字出现次数超过一半,其他数字的count最后肯定会减至0。那么循环结束后的target就是答案。