Day5 : 30 Day Leetcode may challenges

Major_element.cpp

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        /*//Average time complexity is O(n*logn)+1
        sort(nums.begin(),nums.end());
        int n = nums.size();
        //as major element occurs more than [n/2] times,when sorted,compulsorily occurs at mid,as there are n             //elements
        return nums[n/2];
        */
        /*unordered_map<int,int> m;
        int n = nums.size();
        int ans,l = n/2;
        for(int& x : nums){
            m[x]++;
            if (m[x] > l){
                ans = x;
                break;
            }
        }
        return ans;*/
        //Boyer-Moore  algorithm
        //More than half elements is the key
        //Soln is executed with good dp in O(n)
        int major=nums[0], count = 1;
        int n = nums.size();
        //count of major element is always  >= 1
        //In worst cases,major is caught at count = 0
        //i.e when major elemnets are alternatively placed,hen at last count becomes 1,and mojor becomes
        //consider cases 2,1,2,1,2,1,2 and 1,2,1,2,1,2,2
        for(int i=1; i<n;i++){
            if(count==0){
                count++;
                major=nums[i];
            }
            else if(major==nums[i]){
                count++;
            }
            else count--;
            
        }
        return major;
    }
};
        

problem_statement6.txt

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.

Example 1:

Input: [3,2,3]
Output: 3
Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2