How to find number of elements greater than that elements for all elements of the array on the right side.
How to find number of elements greater than that elements for all elements of the array on the right side.
# | User | Rating |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 160 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | orz | 146 |
9 | pajenegod | 145 |
9 | SecondThread | 145 |
Name |
---|
You can use policy based data structure ( Ordered set ) . Then you can traverse the array from the right and keep checking no. of elements using order_of_key(a[i]) . o(nlogn) tc
I guess ordered set not work in case of duplicate element.
It works
4 types of modification you can do Greater Greater Equal Less Less Equal
Also ig it can be done using Divide and conquer ( Merge sort )
Here similar problem on leetcode :
https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/
You can also use Segment Tree, if array value is large in that case you have to normalize it down to <=n range.
Can you explain more as I am not much familiar with segment tree.
you can sort the array in decreasing order keeping their index then you build segment / fenwick tree ans for index i is i — sum(0..j) j denotes index of element in original array then update the value of segment / fenwick tree. sum(0..i) denotes cnt of elements having value less <= element at index i and index < j
Caculate i < j and a_i < a_j. Enumerate from n to 1. For position i, you only need to caculate how many greater than a_i. Use BIT, query(n) — query(a[i]) is answer for position i.
Also, you should normalize a[i] to the range [1,n]
Can you please explain this in a bit more detail and with clarity? Also what is the time complexity of this approach?
i guess find the next greater element for every element to its right and add 1 to the answer* of that element to get the answer for this element.
I guess you are trying to find count of inversions in array which is
if i < j and a[i] > a[j]
This can be done using merge sort along with a simple modification.
Link to understand sol
Statement's really unclear, can you clarify what the problem is?