pnd1901
BAN USERpublic class CountOccuranceEachDup {
private static final Exception START = null;
//binary search : O(log n)
public int getCount(int[] arr,int key,boolean searchFirst){
int low=0,high= arr.length-1, result =-1;
while(low<=high){
int mid= (low+high)/2;
if(arr[mid]==key){
result =mid;
if(searchFirst){
high=mid-1;
}else{
low=mid+1;
}
}else if(key>arr[mid]){
low= mid+1;
}else{
high=mid-1;
}
}
return result;
}
public void printOccurance(int[] arr){
int len=0;
// called for each unique occurrence of the element
while(len<arr.length){
int key = arr[len];
int count;
// search first occurrence in : O(log n)
int firstIndex= getCount(arr,key,true);
// search last occurrence in : O(log n)
int lastIndex= getCount(arr,key,false);
count = lastIndex-firstIndex+1;
System.out.println(key +"->"+count);
len= lastIndex+1;
}
}
public static void main(String[] args){
CountOccuranceEachDup c = new CountOccuranceEachDup ();
int[] arr= {8,8,8,9,9,9,9,9,9,10,10,10,10,10,10,10,10};
c.printOccurance(arr);
}
}
i/p: {8,8,8,9,9,9,9,9,9,10,10,10,10,10,10,10,10};
o/p:
8->3
9->6
10->8
i/p: {8,8,8,8}
o/p : 8>4
Input: parent[] = {1 5 5 2 2 -1 3}
- pnd1901 January 23, 2015Output: 4
The given array represents following Binary Tree
5
/ \
1 2
/ / \
0 3 4
/
6
Input: parent[] = {-1, 0, 0, 1, 1, 3, 5};
Output: 5
The given array represents following Binary Tree
0
/ \
1 2
/ \
3 4
/
5
/
6