题目：
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.
Simple but nlog(n) time complexity
1 public int majorityElement(int[] num) { 2 if (num.length == 1) { 3 return num[0]; 4 } 5 6 Arrays.sort(num); 7 return num[num.length / 2]; 8 }
Linear Time Majority Vote Algorithm 很高级的样子
1 public int majorityElement(int[] nums) { 2 int candidate= 0, count = 0; 3 4 for(int i = 0; i<nums.length; i++ ) { 5 if(count == 0){ 6 candidate= nums[ i ]; 7 count = 1; 8 }else if(candidate == nums[i]){ 9 count++; 10 }else{ 11 count--; 12 } 13 } 14 15 return candidate; 16 }
reference：http://www.programcreek.com/2014/02/leetcode-majority-element-java/
http://www.cs.utexas.edu/~moore/best-ideas/mjrty/
转载于:https://www.cnblogs.com/hygeia/p/4645237.html
相关资源：JAVA上百实例源码以及开源项目