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

how to count the "smaller number" in an array
Автор passworld, 10 лет назад, По-английски

I want to count for every number ,say A[i] ,how many numbers there are that is smaller than Ai with id smaller than i. For example , here is an array: 5 3 7 2 9 6 ,the anwser is 0 0 2 0 4 3 Is there any fast algorithm that can solve this problem? Thank you for your help!

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

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

Use Fenwick Tree, add 1 to tree[A[i] and ask for sum on tree[0...A[i] - 1]

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

    If constraints are too big (A[i] <= 10^9) you can use segment tree with zipping vertexes; It means you will create vertex only when you will need it;

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

the problem can be solved with O(nlogn) complexity using segment tree:

Consider the array b[] where b[i] denotes the number of elements of A that are <=i

Traverse the array A[] from left to right, editing the array b[] on your way by adding 1 on the interval from A[i] to Max number in A[]. The answer for ith number is b[A[i]-1]

please correct me if I am wrong.

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

    And changing limit for A[i] does not make much difference for this solution. You just have to compress all input numbers — say that smallest of them is equal to 1, second smallest is equal to 2 and so an. There will be no more than N different values in array of size N, so you'll end up with array of numbers <=N, even if original numbers were up to 1e18.

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

      You are right, fixed, thanks.

      → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 4   Проголосовать: нравится -8 Проголосовать: не нравится

      Can this sequence "canonicalization" be done faster than sorting and then assigning? I've always used this method when I needed to, and I'm almost sure there is no better method (mainly because you need to know ordinal position for every number), but now I'm thinking about this.

      By "sorting" I include any variant which implies the use of a set/heap or similar things.

      edit: Sometimes I fail to understand why posts get downvoted :|

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

        If you're able to get the position of each element in O(f(n)), then you can sort array in O(f(n) + n), but that's impossible if you use only comparison and f(n) ~< nlogn

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

What you're asking is similar to counting the number of inversions, though the comparison is the other way around. It can be solved with BIT / Segment Tree, like others have said, and also with a modified Merge Sort algorithm.

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

If i didnt get the question wrong it can be solved with a monotonic queue with O(n) time complexity.

EDT: Yes i did get it wrong. Sorry.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

The problem can be solved without compressing the numbers.
Put Fi = 0 for all i <  = N
Sort the pairs Pi = (Ai, i).
Then go from left to right, calculate the answer for Pi.second, which is (F1 + ... + FPi.second - 1). Do this with segment tree.
Then put FPi.second = 1

→ Ответить