karthik.kamaraj
BAN USERHere is the solution with O(MlogN) complexity.
public class CountInteger {
public static void main(String[] args) {
int[] numbers = {8,8,8,9,9,11,15,16,16,16,17,19,19,19,21,22,23};
for (int i = 0; i < numbers.length; i++) {
i = count(numbers, numbers[i], i, numbers.length - 1);
}
}
private static int count(int[] numbers, int key, int lo, int hi) {
//System.out.println(key + " " + lo + " " + hi);
if (numbers[lo] == numbers[hi]) {
System.out.println(numbers[lo] + ":" + ((hi - lo) + 1));
return hi;
}
if (key < numbers[(lo+hi)/2 + 1]) {
return count(numbers, key, lo, (lo+hi)/2);
} else if (key > numbers[(lo+hi)/2 + 1]) {
return count(numbers, key, (lo+hi)/2 + 1, hi);
} else {
System.out.println(numbers[lo] + ":" + ((lo+hi)/2 + 1));
return lo;
}
}
}
- karthik.kamaraj September 18, 2016