Блог пользователя LittleMaster_7

Number of elements less than VAL in an array

Автор LittleMaster_7, история, 10 лет назад, По-английски

Suppose, there is an array of size N. Find number of elements are less than VAL. The array may contain duplicate values.

for example,

array = [ 1 , 2 , 3 , 1 , 2 ]

VAL = 3

So answer will be = 4.

Can it done by STL. (such as set/multiset ) in logarithmic time

I already googled it ,but failed to find solution with STL.

Thanks in advance.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

I assume some preprocessing is allowed, otherwise it is not possible. After sorting each query can be answered in using std::lower_bound.

// Preprocessing part O(n log n)
std::sort(a, a+n);
// query O(log n)
int countLess(int val)
{
    return std::lower_bound(a, a+n, val) - a;
}
→ Ответить
»
10 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

If the numbers are small enough, it can also be done using a binary indexed tree.. Otherwise you can compress all numbers (queries +array) and create a bit over it

→ Ответить
»
10 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Can be done in logn time using Fenwick tree or BIT. I assume that some preprocessing is allowed. As far as I know, femwick tree is not part of STL.

→ Ответить