patternjavaMinor
Find, on a sequence of size L, the number that appears more than L/2 times
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:
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?
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
To get rid of this unwanted result, we need after the loop to increment the counter by
Simplification
Because you are incrementing
General
-
Instead of
-
you should also check if the given array contains any element.
-
declaring multiple variables on one line removes readability.
-
you can initialize
-
Using verbs or verb phrases for methodnames improves readability.
Refactoring
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.