Created
December 24, 2014 06:14
-
-
Save fever324/8382c42d81602bc82b3e to your computer and use it in GitHub Desktop.
Majority Element
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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 class Solution { | |
public int majorityElement(int[] num) { | |
int candidate = num[0]; | |
int counter = 0; | |
for(int a : num) { | |
if(counter == 0) { | |
candidate = a; | |
counter = 1; | |
} else { | |
if(candidate == a) { | |
counter ++; | |
} else { | |
counter --; | |
} | |
} | |
} | |
return candidate; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment