首页 > 代码库 > 169. Majority Element
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.
Solution 1:
比较naive的想法，遍历数组，用map存数和对应的个数。然后再遍历keyset读出那个次数大于n/2的数。
map用来处理重复个数，和记录相同key不同value变化很有用。
注意
int change=res.get(nums[i])+1;
res.put(nums[i],change);
如果直接res.put(nums[i],res.get(nums[i])++)会出错。并不知道具体原因，个人觉得是不能读value的同时还改变value的值。
public class Solution { public int majorityElement(int[] nums) { Map<Integer,Integer> res=new HashMap<Integer,Integer>(); int majority=0; for(int i=0;i<nums.length;i++) { if(!res.containsKey(nums[i])) { res.put(nums[i],1); } else { int change=res.get(nums[i])+1; res.put(nums[i],change); } } for(int num:res.keySet()) { if(res.get(num)>(nums.length/2)) { majority=num; } } return majority; }}
看了discussion的解法，觉得自己的太naive了＝ ＝
Solution 2:
public int majorityElement2(int[] nums) { Map<Integer, Integer> myMap = new HashMap<Integer, Integer>(); //Hashtable<Integer, Integer> myMap = new Hashtable<Integer, Integer>(); int ret=0; for (int num: nums) { if (!myMap.containsKey(num)) myMap.put(num, 1); else myMap.put(num, myMap.get(num)+1); if (myMap.get(num)>nums.length/2) { ret = num; break; } } return ret;}
不需要再用iterator检查keyset，在记录数和次数的同时就可以比较与n/2的大小。
Solution3:
public int majorityElement1(int[] nums) { Arrays.sort(nums); return nums[nums.length/2];}
这尼玛简直是作弊啊！！
Solution4:
Boyer-Moore Majority vote algorithm
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm
核心思想就是存一个counter对应canadiate，如果真的有一个choice次数大于一半，那当循环结束的时候counter必然对应majority choice。
public int majorityElement3(int[] nums) { int count=0, ret = 0; for (int num: nums) { if (count==0) ret = num; if (num!=ret) count--; else count++; } return ret;}
因为题目已经说了肯定存在，所以不用再检查是不是大于一半，退出循环的counter肯定对应着majority 。
169. Majority Element