Open-Algorithms/majority element-II.cpp at master · sharleenclement/Open-Algorithms · 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
68
69
70
71
72
73
74
75
76
77
//Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
#include<bits/stdc++.h>
using namespace std;
  vector<int> majorityElement(vector<int>& nums) {
        int n=nums.size();
        vector<int> ans;
        if(n==0)return ans;
        if(n==1)return nums;

        set<int>s;
        int val1=nums[0];
        int count1=1;
        int val2=nums[0];
        int count2=0;
        for(int i=1;i<n;i++){
           if(nums[i]==val1){
               count1++;
           }else if(nums[i]==val2){
               count2++;
           }else if(nums[i]!=val1&&nums[i]!=val2)
           {
               if(count1==0){
                   val1=nums[i];
                   count1=1;
               }else if(count2==0){
                   val2=nums[i];
                   count2=1;
               }else{
                   count1--;
                   count2--;
               }
           }
        }
        int c1=0;
        for(int i=0;i<n;i++){
            if(nums[i]==val1){
                c1++;
            }
        }

          int c2=0;
        for(int i=0;i<n;i++){
            if(nums[i]==val2){
                c2++;
            }
        }
  //         vector<int> ans;
        if(val1==val2){
            if(c1>n/3){
                ans.push_back(val1);
                return ans;
            }
        }
        else{
            if(c1>n/3){
            ans.push_back(val1);
            }
            if(c2>n/3){
            ans.push_back(val2);
            }
        }
        return ans;
    }
int main(){

int n;
cin>>n;
vector<int> arr(n);
for(int i=0;i<n;i++){
cin>>arr[i];
}
  vector<int> ans=majorityElement(arr);
  for(int i=0;i<ans.size();i++){
    cout<< ans[i]<<" ";
  }
  return 0;
}