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

Number of elements less than VAL in an array

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

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
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +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;
}
→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Thanks a lot, for your effort :)

    But actually its a sub-problem which i trying to solve. To solve that problem i need online solution.

    Any time update value and query is allowed. so preprocess will not work .

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 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

→ Ответить
»
8 лет назад, # |
← 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.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    And I guess it can be done with Fenwick without preprocessing too!

    Anyway the complexity will fall to O(log(N)*log(MAX_VAL)) if used map instead of array [or some other kind of complexity with hash/unordered map :) ]

    → Ответить