Qaz value for each element in a number array is defined as the number of elements whose both value and index are larger than current element. Maximum qaz value of array is the maximum of the qaz values.
Many answers from careercup site use mergeSort algorithm, which is pretty awesome. Since the time complexity requirement is O(nlgn), I assume other sorting approach will work too. Here I use order statistics binary search tree. To better understand order statistics binary search tree, please see my blog here: http://blueocean-penn.blogspot.com/2015/01/order-statistics-binary-search-tree.html
What is the caveat of the following implementation? I will leave it to readers. ;)
Calculate Qaz using binary search tree.
public static class QNode{
int val;
int size;
QNode left, right;
QNode(int v, int s){val = v; size = s;}
//time complexity O(n), n is the tree height
void insert(int target){
size++;
if(target<=this.val){//smaller or equal goes left
if(this.left==null)
this.left = new QNode(target, 1);
else
this.left.insert(target);
}else{
if(this.right==null)
this.right = new QNode(target, 1);
else
this.right.insert(target);
}
}
//time complexity O(n), n is the tree height
int findIndexFor(int value){
int passed = 0;
QNode curr = this;
while(curr!=null){
if(curr.val == value){
return (curr.left==null?0:curr.left.size) + passed;
}else if(curr.val > value){
curr = curr.left;
}else{
passed += (curr.left==null?0:curr.left.size) + 1;
curr = curr.right;
}
}
return -1;
}
}
public static int maxQAZ(int[] nums){
assert(nums != null);
int len = nums.length;
QNode root = new QNode(nums[len-1], 1);
int max = 0;
for(int i=len-2; i>=0; i--){
root.insert(nums[i]);
max = Math.max(max, i- root.findIndexFor(nums[i]));
}
return max;
}
An alternative solution is to modify merge sort to calculate qaz for an array.
//find QAZ using merge sort
public static class Qaz{
int v; int qaz;
public Qaz(int v){this.v = v;}
public String toString(){
return v + "-" + qaz;
}
}
public static void qazBymergeSort(int[] nums){
int len = nums.length;
Qaz[] objs = new Qaz[len];
for(int i = 0; i< len; i++){
objs[i] = new Qaz(nums[i]);
}
mergeSort(objs, 0, len-1);
System.out.println(Arrays.toString(objs));
}
public static void mergeSort(Qaz[] nums, int start, int end){
if(start>=end)
return;
int mid = (start+end)>>>1;
mergeSort(nums, start, mid);
mergeSort(nums, mid+1, end);
merge(nums, start, mid, end);
}
public static void merge(Qaz[] nums, int start, int mid, int end){
Qaz[] temp = new Qaz[end-start+1];
int start2 = mid+1;
int k = temp.length-1;
int add = 0;
while(start<=mid && start2<=end){
if(nums[mid].v<nums[end].v){
temp[k--] = nums[end--];
add++;
}
else{
temp[k] = nums[mid--];
temp[k].qaz = temp[k].qaz + add;
k--;
}
}
while(start<=mid){
temp[k] = nums[mid--];
temp[k].qaz = temp[k].qaz + add;
k--;
}
while(start2<=end)
temp[k--] = nums[end--];
System.arraycopy(temp, 0, nums, start, temp.length);
}
No comments:
Post a Comment