-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmajority-element.cpp
More file actions
74 lines (63 loc) · 1.58 KB
/
majority-element.cpp
File metadata and controls
74 lines (63 loc) · 1.58 KB
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
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int majorityElement(vector<int>& nums) {
// bruteforce
/* int n = nums.size();
for (int i=0; i<nums.size(); i++) {
int cnt = 0;
for (int j=0; j<nums.size(); j++) {
if (nums[i] == nums[j]) {
cnt++;
}
}
if (cnt > n/2) {
return nums[i];
}
} */
// better
/*
map<int, int> result;
// insert the elements in map
for (int i=0; i<nums.size(); i++) {
result[nums[i]]++;
}
// calculating the value which is occurring greater than n/2
for (auto itr: result) {
if (itr.second > nums.size()/2) {
return itr.first;
}
}
return 0; */
// optimal: moore's voting algorithm
int n = nums.size();
int cnt = 0;
int ele = 0;
for (int i=0; i<n; i++) {
if (cnt == 0) {
cnt = 1;
ele = nums[i];
} else if (ele == nums[i]) {
cnt++;
} else {
cnt--;
}
}
int cnt1 = 0;
for (int i=0; i<n; i++) {
if (nums[i] == ele) {
cnt1++;
}
}
if (cnt1 > n/2) {
return ele;
}
return -1;
}
};
int main() {
Solution sol;
vector<int> nums = {1, 2, 5, 6, 6, 6, 6};
cout << sol.majorityElement(nums);
}