Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Boyer–Moore Majority Vote Algorithm Generalization
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Element {
int value;
int count;
};
void CountGreaterThan(int array[], int n, int k) {
if (k <= 1) {
return;
}
struct Element temp[k-1];
for (int i=0; i<k-1; i++) {
temp[i].count = 0;
}
for (int i = 0; i < n; i++) {
int j;
for (j=0; j<k-1; j++) {
if (temp[j].value == array[i]) {
temp[j].count = temp[j].count + 1;
break;
}
}
if (j == k-1) {
int p;
for (p=0; p<k-1; p++) {
if (temp[p].count == 0) {
temp[p].value = array[i];
temp[p].count = 1;
break;
}
}
if (p == k-1)
for (p=0; p<k; p++) {
temp[p].count = temp[p].count + 1;
}
}
}
cout<<"Final Output:"<<endl;
for (int i=0; i<k-1; i++) {
int correct_count = 0;
for (int j=0; j<n; j++) {
if (array[j] == temp[i].value) {
correct_count++;
}
}
if (correct_count > n/k) {
cout << "Number " << temp[i].value<< " with count " << correct_count << endl;
}
}
}
int main() {
int input_array[] = {1, 2, 2, 2, 2, 2, 2, 2, 2, 2};
int size = sizeof(input_array)/sizeof(int);
int k = 2;
CountGreaterThan(input_array,size,k);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment