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.

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/

相关推荐