counting smaller element in O(n)

Revision en1, by DNNJFM, 2016-08-07 08:14:36

Hi, all!

I have an array a[] size of n. note that a[i] in range of 10^18. n in range of 10^6.

How to calculate cnt[] in O(n)?

Here cnt[i] = number of elements in a[] that is no greater than a[i].

For exmaple, a[] = 3 2 3 1 1 2, size n= 6

then cnt[] = 6 4 6 2 2 4.

Is there any algorithm to do that in O(n)?

Tags counting

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English DNNJFM 2016-08-07 08:27:16 59 Tiny change: 't in O(n)?' -> 't in O(n)? or in O(nlogn) if we have to sort?'
en1 English DNNJFM 2016-08-07 08:14:36 366 Initial revision (published)