Using the modification suggested by ffao to Davi'd reply:
public class MaxRepeated {
public static void main(final String[] args) {
maxRepeatedElement(new int[]{1, 2, 1, 2, 3, 2, 3, 1});
maxRepeatedElement(new int[]{1, 2, 1, 2, 3, 1, 3, 1});
maxRepeatedElement(new int[]{1, 2, 1, 2, 4, 1, 1, 3, 1, 3, 1});
maxRepeatedElement(new int[]{1, 2, 1, 2, 2, 1, 2, 3, 1, 2, 1, 2});
}
private static int maxRepeatedElement(final int[] arr) {
int current_candidate = arr[0];
int previous_candidate = arr[0];
int counter = 0, i;
for (i = 0; i < arr.length; ++i) {
if (current_candidate == arr[i]) {
++counter;
} else if (counter == 0) {
previous_candidate = current_candidate;
current_candidate = arr[i];
++counter;
} else {
--counter;
}
System.out.printf(" candidate: %d, counter: %d\n", current_candidate, counter);
}
if (counter == 0) {
System.out.printf(" possible: %d or %d with net freq %d \n", current_candidate, previous_candidate, counter);
final int f1 = frequency(arr, current_candidate);
final int f2 = frequency(arr, previous_candidate);
final int halfLen = arr.length / 2 + (arr.length % 2 == 0 ? 0 : 1);
if (f1 >= halfLen || f2 >= halfLen) {
if (f1 > f2) {
System.out.printf("majority: %d with freq %d \n", current_candidate, f1);
} else {
System.out.printf("majority: %d with freq %d \n", previous_candidate, f2);
}
} else {
System.out.printf("NO majority! \n");
}
} else {
System.out.printf("majority: %d with freq %d \n", current_candidate, frequency(arr, current_candidate));
}
return current_candidate;
}
private static int frequency(final int[] arr, final int candidate) {
int counter = 0;
for (int c : arr) {
counter += candidate == c ? 1 : 0;
}
return counter;
}
}
O(1)
space because the language is not regular. The counter variable required for any solution, takesO(log n)
space. :-)