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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Though it’s marked as easy in Leetcode, it takes me three times before AC.

Still need to be improved, o(n) solution exists.

Solution 1 O(nlogn)

//will nums be empty?

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        if(nums.size() == 1) return nums[0]; //BUG 
        sort(nums.begin(), nums.end());
        int lastNum = nums[0];
        int length = 1;
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] == lastNum){
                length++;
            }
            else{
                lastNum = nums[i];
                length = 1;
            }
            //BUG, move following 2 lines here
            if(length > nums.size() / 2){
                return lastNum;
            }
        }
    }
};

Solution 2 O(n)

We store the first element in the array, and set the times as 1. During the scanning of the array starts at index 1, if the current element is equal to the stored element, add times by 1. Otherwise minus times by 1. If times is 0, change the stored element with current element and set the times as 1 again.

After scanning, the stored elements is the majority.

//Can input be empty?
//What if vector contain 2 elements, so the elements are guranteed to be identical?

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int result = nums[0];
        int num = 1;
        for(size_t i = 1; i < nums.size(); i++){
            if(nums[i] == result){
                num++;
            }
            else{
                num--;
                if(num == 0){
                    result = nums[i];
                    num = 1;
                }
                
            }
        }
        return result;
    }
};