Daily Coding Problem #35

// Given a list of elements, find the majority element, which appears more than half the time(> floor(len(lst) / 2.0)).

// You can assume that such element exists.

// For example, given[1, 2, 1, 1, 3, 4, 0], return 1.

#include <iostream>

#include <string>

#include <vector>

#include <map>

#include <algorithm>

using namespace std;

typedef pair<int, int> pi;

int findMajority(vector<int> lst)

{

int result = 0;

map<int, int> m = map<int, int>();

for (int i = 0; i < lst.size(); ++i)

{

auto temp = m[lst[i]];

if (m.find(lst[i]) != m.end())

{

++m[lst[i]]; // increment the count of this key value

}

else // new key found

{

m.insert(pi(lst[i], 1)); // add the value as the key and start its count at 1

}

}

cout << "values: " << endl;

int max = 0, index = 0;

map<int, int>::iterator itr;

for (itr = m.begin(); itr != m.end(); ++itr)

{

cout << itr->first << ": " << itr->second << endl;

if (itr->second > max)

{

max = itr->second;

index = itr->first;

}

}

int x = floor(lst.size() / 2.0f);

if (m[index] >= x)

{

return index;

}

cout << "Error" << endl;

return -1;

}

int main()

{

vector<int> lst = { 1, 2, 1, 1, 3, 4, 0 };

int result = findMajority(lst);

cout << "Majority Element: " << result << endl;

return 0;

}