current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 5 down vote favorite

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));
    }
}
share|improve this question
    
Use the test input int[] a9 = {1, 2, 2, 1, 3, 3, 1, 4, 4, 1, 5, 5, 5}; ... what's the result? –  rolfl Mar 30 '14 at 17:42
    
Well there is a javadoc stating 'If such a number does not exist, then results are unpredicatable.' Is that what you were upto ? –  JavaDeveloper Mar 30 '14 at 18:04
    
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(...) –  rolfl Mar 30 '14 at 18:51
1  
@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... –  Ocelot20 Mar 30 '14 at 19:07
    
@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'. –  rolfl Mar 31 '14 at 12:37

2 Answers 2

up vote 6 down vote

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.

share|improve this answer
    
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? –  Simon Forsberg♦ Mar 30 '14 at 20:35
    
@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? –  Uri Agassi Mar 31 '14 at 6:35
    
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. –  Simon Forsberg♦ Mar 31 '14 at 9:57
    
@SimonAndréForsberg thanks, fixed the APIs. –  Uri Agassi Mar 31 '14 at 10:14
up vote 5 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.