dominator code to be reviewed in Java/C++

Question

Dominator is a value which occurs on more than half positions in an array. For instance in the array: [3, 4, 3, 2, 3, -1, 3, 3] 5/8 > 0.5

The value 3 occurs in 5 out of 8 positions. , so 3 is a dominator: In this array the dominator occurs on indexes : 0, 2, 4, 6 , 7. Write a function int dominator(int[] A); that given an array returns any index on which its dominator occurs. For example, given the array as above, the function may return the value 0, or the value 2, or 4, or 6, or 7. If there is no dominator, the function should return the value -1.

I implemented a solution to this as follows-Is there any better solution to this? Efficiency wise?

int dominator(int[] A){
//create a HashMap of (key,Value) pair as (arrayElementValue,count)
// for (i=0;i<A.length;i++) hashMap(A[i],hit+1)
//i.e on each encounter of the array element, we increase the count of the hit.
//Now for the second iteration, I checked if the element in hashMap value pair > 0.5
//for(i=0;i<hashMap.length;i++) if(hashMap.getValue(i)/A.length >0.5) return hashMap.getKey(); 
//else
//return -1 
}

Please let me know if there is a better alternative to this/..Thank you.

Answer 1

You don't need two iterations. In your function, calculate what half of the length of the array is. Then, iterate through, using a Hashmap and increase the hit count but right after you increase it, check to see if it is greater than half of the length of the array, if so, return the index.

Answer 2

Not only do you not need two loops, but you can return immediately if you find that one entry exceeds half. Also, if you take this approach you can return -1 after the loop finishes since no entry is a dominator.

int dominator(int[] A) {
  for (i=0;i<A.length;i++) {
    hashMap[A[i]]++;
    if (hashMap[A[i]] > A.length/2) return i;
   }
  return -1;
}

Answer 3

#include <iostream>
#include <map>
#include <ostream>
using namespace std;
int main(){
int a[]={3,4,3,2,3,-1,3,3};
 int n=sizeof(a)/sizeof(a[0]);
map<int,int>M;
 for (int i=0;i<n;i++){
  ++M[a[i]];
   }
 map<int,int>::iterator it;
 for (it=M.begin();it!=M.end();it++){
  if ((it->second)>(n/2)){
   cout<<it->first<<endl;
   break;

  }


 }


  return 0;
}