Given an array of integers, the majority number is the number that occurs
Have you met this question in a real interview? more than half
of the size of the array. Find it.
Yes
Example
Given
[1, 1, 1, 1, 2, 2, 2]
, return 1
Challenge
O(n) time and O(1) extra space
public class Solution {
/**
* @param nums: a list of integers
* @return: find a majority number
*/
public int majorityNumber(ArrayList<Integer> nums) {
// write your code
if(nums == null || nums.size() == 0) return 0;
int count = 1, cur = nums.get(0);
for(int i = 1; i < nums.size(); i++){
if(nums.get(i) == cur){
count++;
} else{
count--;
}
if(count == 0){
count = 1;
cur = nums.get(i);
}
}
return cur;
}
}
No comments:
Post a Comment