counting smaller element in O(n)

Правка en1, от 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)?

Теги counting

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский 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 Английский DNNJFM 2016-08-07 08:14:36 366 Initial revision (published)