LeetCode OJ 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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

【思路1】java HashMap

我们用java的HashMap,把数组中的值做为键,把元素的数目作为值。如果出现了一个元素的数目大于nums.length/2,则返回该值。代码如下:

 public class Solution {
public int majorityElement(int[] nums) {
if(nums.length==0 || nums==null) return 0;
Map<Integer, Integer> map = new HashMap<>(); for(int i = 0; i < nums.length; i++){
if(map.containsKey(nums[i])){
if(map.get(nums[i])+1 > nums.length/2) return nums[i];
map.put(nums[i], map.get(nums[i])+1);
}
else
map.put(nums[i], 1);
}
return nums[0];
}
}

【思路2】

由于数组中肯定存在一个majority number。因此我们可以遍历数组,如果找到一对值不同的元素就把他们删除,那么最后剩下的一定majority number。这种算法叫Moore’s Voting Algorithm,由Robert S.Boyer 和J Strother Moore于1980年发明,是线性时间复杂度。

举个例子:[1,2,3,1,1,1] (1,2)是一对不相同的元素,(3,1)是另一对不相同的元素,那么剩下的1肯定是majority number。代码如下:

 public class Solution {
public int majorityElement(int[] nums) {
if(nums.length==0 || nums==null) return 0;
int count = 0;
int result = 0; for(int i = 0; i < nums.length; i++){
if(count == 0){
result = nums[i];
count = 1;
}
else{
if(nums[i] == result){
count ++;
}
else count --;
}
}
return result;
}
}

当然,这种算法对于存在主元素的数组是有效的,如: A A A C C B B C C C B C C

它肯定能返回主元素C。但是,如果不存在主元素,那么得到的结果就跟遍历顺序有关了。如: A A A C C C B

如果是从左到右,那么结果是B,如果是从右到左,那么结果是A。

上一篇:01-老马jQuery教程-jQuery入口函数及选择器


下一篇:LeetCode Javascript实现 169. Majority Element 217. Contains Duplicate(两个对象比较是否相等时,如果都指向同一个对象,a==b才是true)350. Intersection of Two Arrays II