To achieve this result I am about to implement an algorithm based on the discussion that you can read in a paper available on Codility. Look at the end of that document, for a Python function named goldenLeader.
In a few words, the idea is that if a dominator exists, we could discard couples of different elements, and in the end, we should ends up with having spared at least one dominator element. If no dominator exists, we'll find out we have throw away all the elements looking for it.
However, our function should not return just the dominant value, but an index of the original vector that refers to an element with such a value. So we need to twist a bit that algorithm.
typedef std::pair<unsigned, int> ValInd; // 1
int solution(const std::vector<int>& input)
{
int count = 0; // 2
ValInd candidate; // 3
for (unsigned i = 0; i < input.size(); ++i)
{
if (count == 0) // 4
{
count = 1;
candidate.first = input[i];
candidate.second = i;
}
else // 5
{
count += (candidate.first == input[i]) ? 1 : -1;
}
}
if (count == 0) // 6
return -1;
if (std::count(input.begin(), input.end(), candidate.first) > (int) input.size() / 2)
return candidate.second;
return -1;
}
1. I need to remember the current value and the index where I have found it.2. I am going to count how many elements, supposedly being dominators, I have found that are not yet matched with non-dominator. I could have pushed them on a stack, but it is obviously cheaper doing in this way.
3. Here I am going to store the current candidate.
4. No previous candidate survived the looping, the current element is chosen.
5. I have a candidate, I compare it against the current element. If they have the same value, I increase the counter, otherwise I decrease it.
6. If there is no pending candidate, I am sure there is no dominant value. Otherwise I count how many elements with the candidate value are in the input collection. If they are enough, bingo.
