导航
导航
文章目录
  1. 题目
  2. 翻译

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.

翻译

给出一个大小为n的数组,找出其中的多数元素。
多数元素是指出现 ⌊ n/2 ⌋ 次以上的元素。
你可以认为数组是非空的,并且数组中多数元素一定存在。

《数学之美》上的原题,用的Moore’s Voting Algorithm:

1
// todo

其实解法比较多:
1、排序
因为题中说可以认为一定存在,所以取中间位置的元素即可:

1
2
3
4
5
6
public class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}

Runtime: 3 ms
2、遍历数组
记录每个元素出现的次数,次数大于n/2即为所求:

1
2
3
4
5
6
7
8
9
public class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Integer> times = new HashMap<Integer, Integer>();
for (int i : nums) times.put(i, times.get(i) == null ? 1 : times.get(i) + 1);
for (Map.Entry<Integer, Integer> entry : times.entrySet())
if (entry.getValue() > nums.length / 2) return entry.getKey();
return 0;
}
}

Runtime: 34 ms
3、顺序取
分别计算次数,因为所求出现次数大于1/2,所以取到可能性很大:

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int majorityElement(int[] nums) {
for (int i = 0; ; i++) {
int times = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[j] == nums[i]) times++;
}
if (times > nums.length / 2) return nums[i];
}
}
}

超时……
4、比较有趣,随机选择一个元素,然后统计其出现次数判断是否为所求。期望查找次数<2,平均时间复杂度为O(n);

参考:
http://www.cnblogs.com/fanyabo/p/4178993.html