yeppe - 1 year ago 43

Java Question

I want to reduce the complexity of this program and find count of elements greater than current/picked element in first loop (

`array[]`

`solved[]`

But If someone can suggest a better collection here in java that can reduce the complexity of this code that would also be highly appreciated.

`for (int i = 0; i < input; i++) {`

if (i < input - 1) {

count=0;

for (int j = i+1; j < input; j++) {

System.out.print((array[i])+" ");

System.out.print("> ");

System.out.print((array[j]) +""+(array[i] > array[j])+" ");

if (array[i] > array[j]) {

count++;

}

}

solved[i] = count;

}

}

for (int i = 0; i < input; i++) {

System.out.print(solved[i] + " ");

}

Say I have 4 elements in my

array[] -->86,77,15,93

solved[]-->2 1 0 0

2 because after 86 there are only two elements 77,15 lesser than 86

1 because after 77 there is only 15 lesser than 77

rest 15 <93 hence 0,0

Answer

So making the code simpler and making the code faster aren't necessarily the same thing. If you want the code to be simple and readable, you could try a sort. That is, you could try something like

```
int[] solved = new int[array.length];
for (int i = 0; i < array.length; i++){
int[] afterward = Arrays.copyOfRange(array, i, array.length);
Arrays.sort(afterward);
solved[i] = Arrays.binarySearch(afterward, array[i]);
}
```

What this does it it takes a copy of the all the elements after the current index (and also including it), and then sorts that copy. Any element less than the desired element will be beforehand, and any element greater will be afterward. By finding the index of the element, you're finding the number of indices before it.

A disclaimer: There's no guarantee that this will work if duplicates are present. You have to manually check to see if there are any duplicate values, or otherwise somehow be sure you won't have any.

**Edit:** This algorithm runs in *O(n ^{2} log n)* time, where

Source (Stackoverflow)