An ordinary problem with an extraordinary(maybe) complexity! Help needed!

Правка en2, от Tribbiani, 2017-07-12 16:15:09

Suppose an array contains n elements. The elements is in the range 109. We want to know, for every element in the array, the position of the leftmost element that is smaller than that one.

An example:

Position: 1 2 3 4 5 6 7 The array: 20 3 10 5 1 9 100 Answer: 0 0 2 2 0 2 1

Can this problem be done in O(n)?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский Tribbiani 2017-07-12 16:22:43 47
en3 Английский Tribbiani 2017-07-12 16:22:10 4
en2 Английский Tribbiani 2017-07-12 16:15:09 39 Tiny change: 'elements. We want ' -> 'elements. The elements is in the range $10^{9}$. We want '
en1 Английский Tribbiani 2017-07-12 16:10:21 418 Initial revision (published)