If we have array of element, what is the efficient way to calculate index of each element after sorting that array? is there any way to efficiently reuse sort function in c++ or java?
for example:
double[] array=[".2",".6",".3",".5",".1"];
I want something like this:
ans= [ 1, 4, 2, 3, 0 ];
that's because after sort .2 place in index 1, .6 place in index 4, .3 place in index 2 and so on.
This will accomplish what you are looking for in O(n log n), there most likely is a better way:
double[] arr = {0.2, 0.6, 0.3, 0.5, 0.1};
Integer[] intermediateIndices = new Integer[arr.length];
Integer[] finalIndices = new Integer[arr.length];
for (int i = 0; i < arr.length; i++) {
intermediateIndices[i] = i;
finalIndices[i] = i;
}
Arrays.sort(intermediateIndices, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return Double.compare(arr[o1], arr[o2]);
}
});
Arrays.sort(finalIndices, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return intermediateIndices[o1] - intermediateIndices[o2];
}
});
System.out.println(Arrays.toString(intermediateIndices));
System.out.println(Arrays.toString(finalIndices));
// [4, 0, 2, 3, 1]
// [1, 4, 2, 3, 0]
O(1)after sorting. I don't want to search for the element each time.