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.
hashmap的方法，此方法需要注意的就是可以在loop里面就判断返回了，不用iterator。因为最后一个加完之后major肯定是大于n/2的。
public class Solution { public int majorityElement(int[] nums) { HashMap<Integer, Integer> h = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (h.containsKey(nums[i])) { h.put(nums[i], h.get(nums[i]) + 1); } else { h.put(nums[i], 1); } if (h.get(nums[i]) > nums.length/2) { return nums[i]; } } return 0; } }
2.
神奇的算法。。。
public class Solution { public int majorityElement(int[] nums) { int major = nums[0]; int count = 1; for (int i = 1; i < nums.length; i++) { if (count == 0) { count++; major = nums[i]; } else if (major == nums[i]) { count++; } else { count--; } } return major; } }
3.
可以排序之后返回中间值。
4.
还有bit manipulation的没做，到时候回顾一下。。。
原文：http://www.cnblogs.com/aprilyang/p/6286581.html