Monday, June 29, 2015

Majority Number

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.
Have you met this question in a real interview? 
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