classSolution{public:intmajorityElement(vector<int>&nums){intn=nums.size();intmajorityCount=n/2;// Is any number greater than this, that's our answer// This picks one number at a timefor(inti=0;i<n;i++){intcount=0;// Store the frequency of the number picked// This will count how many the times the picked number comesfor(intj=i;j<n;j++){// If we see the picked number in the arrayif(nums[i]==nums[j]){count++;// Increament the count}// Check, it is greater or not, that `majorityCount`if(count>majorityCount){returnnums[i];// If it is, then return our picked number}}}return-1;// this is not required, but for compiler}};
classSolution{public:intmajorityElement(vector<int>&nums){intn=nums.size();// This map will store frequencies of the numbers we encounter// Key -> number, Value -> frequencyunordered_map<int,int>countsMap;intmajorityCount=n/2;// If frequency of any number greater than this, is our answer// We pick each number at a timefor(intnum:nums){// It will increase the count of the `num` in map, whenever we encounter it// Or if the number is not in the map, it will automatically store the `num` with 0, before increamentcountsMap[num]++;// If the `num` is greater than `majorityCount`if(countsMap[num]>majorityCount){returnnum;// Then return the `num`}}return-1;// This is not required, but it is for compiler only}};
classSolution{public:intmajorityElement(vector<int>&nums){// Our candidate is not fixed yet, so the count is 0intcandidate=0;intcount=0;// We will pick each number at a timefor(intnum:nums){// If the `count` is 0, so we set our `candidate`// to current `num` as our new `candidate`if(count==0){candidate=num;}// If we see a num equals to candidate, increment the count// or if we any different num, decrement the countif(candidate==num){count++;}else{count--;}}// The algorithm will give the answer easily, cause if the majority element exist// It will cancel out all the other numbers, and left candidate will be our answerreturncandidate;}};
Warning
LINK
You are about to visit a link which has been flagged with the above content warnings. Do you wish to continue?