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.

Solution: While traversing the array, we need a count variable that keeps track of how many times “last_number” appears in the array. “last_number” will be changed into the nums[i] if count = 0. However, the success of the method is the existence of the majority element. If it is not guaranteed, then this method will fail.

public class Solution {
    public int majorityElement(int[] nums) {
        
        int count = 1; 
        int last_number = nums[0]; 
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == last_number ) {
                count++; 
            } else if (nums[i] != last_number) {
                count--; 
            }
            
            if (count == 0) {
                last_number = nums[i];
                count++;
            }
        }
        return last_number; 
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s