Description
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.
Solution
Sort, time O(nlogn), space O(1)
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
}
HashMap
简直懒得写
Majority Voting Algorithm, time O(n), space O(1)
Majority Vote Alogrithm
A Linear Time Majority Vote Algorithm
算法的具体思路是：假设在给定长度为 n 的数组中，Majority Element 出现的次数是 k 次，那么非 Majority Element 的出现次数就为 n-k。如果我们能去掉这 n-k 个元素那么剩下的就全部是 Majority Element 了。
我们可以遍历数组,当碰到两个不一样的数字时,我们将这两个数字同时丢弃这两个数字中可能有一个为 Majority Element,也可能两个都不为Majority Element.因为k 大于 n/2,所以在最差情况下(每次移除不同数字时都包含一个Majority Element),我们仍然能够保证最后得到的数字是Majority Element.
在网上看到的很多资料中，对这一步的解释都是略微有些问题的。很多人简单的将这一步解释为：找到一个Majority Element，随后找到一个 非Majority Element，并将他们一并移除，这其实是错误的。我们在循环的时候，并没有办法判定当前的数字是否为 Majority Element，所以在移除的时候，我们可能是移除了一个 Majority Element 和一个 非Majority Element，也有可能移除的是两个非Majority Element。所以最后 count 的值是不确定的，但是它能够保证在最差情况下，剩余的仍然是 Majority Element。例如，[1,2,3,3,3] 和 [1,3,2,3,3] 这两个数组最后得到的 count 分别为 3 和 1，但是这并不影响答案的正确性。
这也是前面提到的Majority Element的数量必须大于n/2的原因.
很容易算出最后剩余的Majority Element个数最少为： n - ((n - k) + (n - k)) = 2k - n。
class Solution {
public int majorityElement(int[] nums) {
int major = 0;
int count = 0;
for (int i = 0; i < nums.length; ++i) {
if (count == 0) {
major = nums[i];
++count;
} else if (major == nums[i]) {
++count;
} else {
--count;
}
}
return major;
}
}
