[题目]
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.
[题目解析] 根据题目需要求数组中，出现次数过半的元素。最容易想到的就是直接的去遍历数组计数，然后出现次数过半的即为所求。
public int majorityElement(int[] nums) { int result = 0; HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); for(int i = 0; i < nums.length; i++){ int num = nums[i]; if(map.containsKey(num)){ map.put(num, map.get(num) + 1); }else{ map.put(num,1); } f(map.get(num) > (nums.length)/2){ result = num; } } return result; }
还有没有其他方法呢？比较容易能想到，如果是一个有序数组，那么中间位置的数一定就是所求。我们可以对数组进行排序。
public int majorityElement(int[] nums) { Arrays.sort(nums); return nums[nums.length/2]; }
此外，还有一种比较巧妙的方法。
[LeetCode] NO. 169 Majority Element
原文：http://www.cnblogs.com/zzchit/p/5782497.html