DSA/majorityElement.cpp at main · Muskanagarwal06/DSA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//Brute Force Approach
//Time Complexity O(n^2)
// int main(){
//     vector<int> nums={2,3,4,5,2,3,2,2,2,2,3,2};
//     int n=nums.size();
//     for (int val:nums){
//         int freq=0;
//         for(int ele: nums){
//             if(val==ele){
//                 freq++;
//             }
//         }
//         if(freq>n/2){
//             cout<<"Majority Element: "<<val;
//             break;
//         }
//     }
//     return 0;
// }


//Time Complexity O(nlogn+n)
// int main(){
//     vector<int> nums={2,4,3,6,5,5,4,4,4,4,4,4,4,5};
//     int n=nums.size();
//     sort(nums.begin(),nums.end());
//     int freq=1,val=nums[0];
//     for (int i=1 ; i<n ; i++){
//         if(nums[i]==nums[i-1]){
//             freq++;
//         }
//         else{
//             freq=1;
//             val=nums[i];
//         }
//         if(freq>n/2){
//             cout<<"Majority Element: "<<val;
//             break;
//         }
//     }
//     return 0;
// }

//Moore's Voting Algorithm
//Time Complexity O(n)
int main(){
    vector<int> nums={2,3,3,2,1,2,3,3,3,3,3,2,2};
    int freq=0;
    int ans=0;
    for (int val : nums){
        if(freq==0){
            ans=val;
        }
        if (val==ans){
            freq++;
        }
        else{
            freq--;
        }
    }
    cout<<ans;
}