+ 1
Given a sorted Array A(may contain duplicates):Fill array B such that B contains elements from A with increasing frequencies.
Array A has elements in NON decreasing order.Array B must contain elements from A(duplicates not allowed in B) in increasing order of their frequency.If two or more elements have same frequency then array B should contain that element first which appears first in A. example: Array A: 1 1 2 2 2 3 3 4 5 Array B: 4 5 1 3 2 (EXPECTED) Try to Solve it in as efficient way as you can.
3 odpowiedzi
+ 2
the array A is sorted , so you can use the binary search to get the index of each element in the case of the tie .
this is an implement of this idea , hope this will be helpful.
https://code.sololearn.com/cn5sdrr1S2y5/#cpp
+ 1
@Mohamed Hamada
what is the complexity of your solution?
also you have used freq[v[i]] .What if v[i](User input) have -ve values?
+ 1
O(NlogN).
it's ok if v[i] is a -ve ... i'm using the map !
about map (is needed )
http://www.cplusplus.com/reference/map/map/