HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Find, on a sequence of size L, the number that appears more than L/2 times

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
numberthesizethanmoresequenceappearsthatfindtimes

Problem

Yes, yet another challenge on CodeEval!

This one has the purpose of finding the major element of a sequence: the element which appears in a sequence of size L more than L/2 times. I have this:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main (String[] args) throws IOException {
        File file = new File(args[0]);
        BufferedReader buffer = new BufferedReader(new FileReader(file));
        String line;
        String[] numbersRaw;
        int[] numbers;
        while ((line = buffer.readLine()) != null) {
            line = line.trim();
            numbersRaw = line.split(",");
            numbers = new int[numbersRaw.length];
            for(int i = 0; i  bigCounter) {
                    big = arr[i];
                    bigCounter = counter;
                }                        
                counter = 0;
            }            
        }
        if(bigCounter > arr.length / 2) {
            return big + "";
        }
        return "None";
    }    
}


I have this solution, with appears to solve the challenge - however I think its performance is a bit sluggish (measured running time is about 1300 milliseconds). Is there any way to improve this?

Solution

Bug / unexpected result

Focusing only on mostFrequentElement() method

Assume passing the array {2,2,3,3,3} this will result in "None" but the correct result should be "3".

To get rid of this unwanted result, we need after the loop to increment the counter by 1 and add a check

counter++;
if (counter > bigCounter) {
    big = arr[arr.length - 1];
    bigCounter = counter;
}


Simplification

Because you are incrementing counter wether the if condition is true or false this can be simplified to

for (int i = 0; i  bigCounter) {
            big = arr[i];
            bigCounter = counter;
        }                        
        counter = 0;
    }            
}


General

-
Instead of return big + ""; you should use the return String.valueOf(big); because it is more readable.

-
you should also check if the given array contains any element.

-
declaring multiple variables on one line removes readability.

-
you can initialize bigCounter with 0 because counter is always > 0.

-
big and bigCounter aren't good names. Better name them mostFrequentElement and mostFrequentElementCounter and rename the method to getMostFrequentElement.

Using verbs or verb phrases for methodnames improves readability.

Refactoring

private static String getMostFrequentElement(int[] arr) {
    if (arr.length == 0) {
        return "None";
    }

    Arrays.sort(arr);

    int counter = 0;
    int mostFrequentElement = -1;
    int mostFrequentElementCounter = 0;

    for (int i = 0; i  mostFrequentElementCounter) {
                mostFrequentElement = arr[i];
                mostFrequentElementCounter = counter;
            }
            counter = 0;
        }
    }

    counter++;
    if (counter > mostFrequentElementCounter) {
        mostFrequentElement = arr[arr.length - 1];
        mostFrequentElementCounter = counter;
    }

    if (mostFrequentElementCounter > arr.length / 2) {
        return String.valueOf(mostFrequentElement);
    }
    return "None";
}

Code Snippets

counter++;
if (counter > bigCounter) {
    big = arr[arr.length - 1];
    bigCounter = counter;
}
for (int i = 0; i < arr.length - 1; i++) {
    counter++;
    if (arr[i] != arr[i + 1]) {
        if (counter > bigCounter) {
            big = arr[i];
            bigCounter = counter;
        }                        
        counter = 0;
    }            
}
private static String getMostFrequentElement(int[] arr) {
    if (arr.length == 0) {
        return "None";
    }

    Arrays.sort(arr);

    int counter = 0;
    int mostFrequentElement = -1;
    int mostFrequentElementCounter = 0;

    for (int i = 0; i < arr.length - 1; i++) {
        counter++;
        if (arr[i] != arr[i + 1]) {
            if (counter > mostFrequentElementCounter) {
                mostFrequentElement = arr[i];
                mostFrequentElementCounter = counter;
            }
            counter = 0;
        }
    }

    counter++;
    if (counter > mostFrequentElementCounter) {
        mostFrequentElement = arr[arr.length - 1];
        mostFrequentElementCounter = counter;
    }

    if (mostFrequentElementCounter > arr.length / 2) {
        return String.valueOf(mostFrequentElement);
    }
    return "None";
}

Context

StackExchange Code Review Q#77492, answer score: 4

Revisions (0)

No revisions yet.