Problem
write a O(n) based code to find the major element in an array.
array is 6,7,7,8,8,2,3,8,8,11,23,8,8,,3,3,4,4,4
output should be 8 because it is repeated max no. of times in the array.
C/C++
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find major number
Created Data : 28-07-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <hash_map>
#include <cassert>
using namespace std;
bool FindMajorNum(int* arr, int len, int& majorNum)
{
int maxCount(0);
hash_map<int, int> hm;
for(int i = 0; i < len; ++i){
if(hm.find(arr[i]) != hm.end()){
hm[arr[i]] ++;
}
else{
hm[arr[i]] = 1;
}
if(maxCount < hm[arr[i]]){
maxCount = hm[arr[i]];
majorNum = arr[i];
}
}
return (maxCount >= (len + 1) / 2);
}
void DoTest(int* arr, int len)
{
assert(arr != NULL && len > 0);
cout << "The array is " << endl;
for(int i = 0; i < len; ++i){
cout << setw(4) << arr[i];
}
cout << endl;
int majorNum;
if(FindMajorNum(arr, len, majorNum)){
cout << "Find major number: " << majorNum << endl;
}
else{
cout << "Nothing is found" << endl;
}
cout << "------------------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr[] = {6,7,7,8,8,2,3,8,8,11,23,8,8,3,3,4,4,4};
DoTest(arr, sizeof(arr)/sizeof(int));
int arr1[] = {6};
DoTest(arr1, sizeof(arr1)/sizeof(int));
int arr2[] = {6,7};
DoTest(arr2, sizeof(arr2)/sizeof(int));
int arr3[] = {6, 7, 8};
DoTest(arr3, sizeof(arr3)/sizeof(int));
int arr4[] = {6,7,7,8,8,2,3,8,8,11,23,8,8,3,3,8,8,8};
DoTest(arr4, sizeof(arr4)/sizeof(int));
return 0;
}
Output
The array is
6 7 7 8 8 2 3 8 8 11 23 8 8 3 3 4 4 4
Nothing is found
------------------------------
The array is
6
Find major number: 6
------------------------------
The array is
6 7
Find major number: 6
------------------------------
The array is
6 7 8
Nothing is found
------------------------------
The array is
6 7 7 8 8 2 3 8 8 11 23 8 8 3 3 8 8 8
Find major number: 8
------------------------------
Press any key to continue . . .