example- Array–>{12,32,45,11}
Output–>2 3 4 1
Please suggest me solution without sorting
One way is using priority queue and HashMap, Store all the elements in Hashmap with Key as the element and value as it index in given array, then insert all the elements in priority queue and start dequeuing while keeping a count which will be the relative index of the element now form the new array using the Hashmap. Basically sorting is taking place, O(n log n) solution is the efficient one I guess.
2 Likes
i used treeset,firstly insert elements in treeset and then from treeset to hashmap and after that find the elememt account to thier key(which is element itself) and update the value at desired position,what about the complexity with this approach?
HashMap - yes, but actually you don’t need exactly priority queue (aka Heap Sort ), any other sorting algorithm working the same way and could have better run time than priority queue.
Such as Merge Sort or Quick Sort, both of them are O(n log n), but on average quicker than Heap Sort.
May be your task is good for bucket sort or radix sort, they could have linear run time or may be even sublinear