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出现的次数，如果下一个数还是这个数就将count加1，否则减1。如果count为0，就以下一个数为target并重新开始计算count。最后输出target。因为目标数字出现次数超过一半，其他数字的count最后肯定会减至0。那么循环结束后的target就是答案。