Voting Algorithm

Question

Find the element the occurs more than \$\dfrac{n}{2}\$ times in an input array, where \$n\$ is input array length.

I'm looking for code review, optimizations and best practices.

 public final class VotingAlgorithm {
 // non-instantiable.
 private VotingAlgorithm() {} 
 /**
 * Returns the number which occurs more than n/2 times.
 * If such a number does not exist, then results are unpredicatable.
 * 
 * @param a the input array
 * @return the number occuring more than n/2 times.
 */
 public static int maxElement(int[] a) {
 int maxElementIndex = 0;
 int counter = 1;
 for (int i = 1; i < a.length; i++) {
 if (a[maxElementIndex] == a[i]) {
 counter++;
 } else {
 counter--;
 }
 if (counter == 0) {
 maxElementIndex = i;
 counter++;
 }
 }
 return a[maxElementIndex];
 }
 public static void main(String[] args) {
 int[] a1 = {1, 2, 3, 1, 1, 1};
 assertEquals(1, maxElement(a1));
 int[] a2 = {2, 3, 1, 1, 1, 1};
 assertEquals(1, maxElement(a2));
 int[] a3 = {1, 1, 1, 1, 2, 3};
 assertEquals(1, maxElement(a3));
 int[] a4 = {1, 2, 1, 3, 1, 1};
 assertEquals(1, maxElement(a4));
 int[] a5 = {1, 2, 3, 4, 1, 1, 1};
 assertEquals(1, maxElement(a5));
 int[] a6 = {2, 3, 4, 1, 1, 1, 1};
 assertEquals(1, maxElement(a6));
 int[] a7 = {1, 1, 1, 1, 2, 3, 4};
 assertEquals(1, maxElement(a7));
 int[] a8 = {1, 2, 1, 3, 1, 4, 1};
 assertEquals(1, maxElement(a8));
 }
}

• rolfl: Use the test input int[] a9 = {1, 2, 2, 1, 3, 3, 1, 4, 4, 1, 5, 5, 5}; ... what's the result?
• JavaDeveloper: Well there is a javadoc stating 'If such a number does not exist, then results are unpredicatable.' Is that what you were upto ?
• rolfl: You are right, the JavaDoc does say that, and, you are right, the results are unpredictable. As a consequence, this question gets my -1 vote because there is no way for a calling program to know whether it has a right result or not.... The function should be called mightGetMaxElement(...)
• Ocelot20: @rofl: I'm new here so maybe I misunderstand the nature of this site, but a -1 vote seems a bit spiteful. Your issue with the question appears to be a criticism of the code (the whole point of the site), not a criticism of the question itself...
• rolfl: @Ocelot20 - This question does not show any research effort, is unclear, or is not useful ... (tool-tip for down-vote button). I believe this question is neither 'clear', nor 'useful'.

Answer 1

Your code is very clever, perhaps a little too clever... It almost looks like you wrote the code first, and then asked yourself - what can this achieve?
As @rolfl said - as it is currently written - the code is all but useless, because most of the time the result is unpredictable. Calling this method will return a value, which could either have more than half the length of occurrences, or... not?

You could achieve at least as much information with the same complexity, by keeping more complete score.

Here is an example, where you can save the count of each element, and keep the one with most occurrences:

public int elementWithMostOccurrences(int[] inputArray) {
 HashMap<Integer, Integer> occurrenceCount = new HashMap<Integer, Integer>();
 int currentMaxElement = inputArray[0];
 for (int i = 1; i < inputArray.length; i++) {
 Integer elementCount = occurrenceCount.get(inputArray[i]);
 if (elementCount != null)) {
 occurrenceCount.put(inputArray[i], elementCount + 1);
 if (elementCount >= occurrenceCount.get(currentMaxElement)) {
 currentMaxElement = inputArray[i];
 }
 } else {
 occurrenceCount.put(inputArray[i], 1);
 }
 }
 // if you want to return the element only if it has more than half the array size you can:
 // if (occurrenceCount.get(currentMaxElement) > inputArray.Length / 2) { ... }
 return currentMaxElement;
}

This example is also \$O(n)\$ complexity, but gives a valuable result every time.

• Simon Forsberg: Even though you have a very good alternative code here, your code is C# while the question is Java. Want some help in translating it to Java?
• Uri Agassi: @SimonAndréForsberg - Woops... didn't even notice I switched languages... Thanks for pointing it out... I'm a little rusty with auto-boxing, could you please verify my java version?
• Simon Forsberg: Use HashMap instead of Hashtable, and use the .get and .put methods of it. You can't access it by indexes directly. besides that, it looks fine.

Answer 2

The JavaDoc and the method names do not agree.

The method name maxElement implies the method will get either:

1. the element that occurs most frequenly
2. the element with the largest value

This function may, or may not, do both.

The JavaDoc indicates that this function will return the value that occurs more more than half-the-time, and that if there is no such element, the result is undefined.

This makes the method useless, because anyone calling the method will then have to re-scan the entire data set to see whether the method is returning a right answer, or an undefined answer.

Since repeating all the work to check whether the method produced a reliable result or not is required anyway, you may as well do it in the method itself, and then return a result which removes the non-determinism.