Counting inversions in an array - special case

Question

The number of inversions for the array indicates how far (or close) the array is sorted. If the array is already sorted, then the number of inversions is 0. If the array is sorted in the reverse order, then the number of inversions is the maximum. Formally speaking, two elements a [i] and a [j] form an inversion if a [i]> a [j] and i <j Example: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1 ), (4, 1), (4, 3).

Now in O (n log n) there are various algorithms.

There is a special case when an array has only 3 types of elements - 1, 2 and 3. Now can we calculate the inversions in O (n)?

For example, 1,1,3,2,3,1,3

Answer 1

, . 3 a,b,c, a - 1, , b - 2, , c - 3, . , ( , arr, n, 1, - )

    no_of_inv = 0
    a = 0
    b = 0
    c = 0
    for i from 1 to n:
       if arr[i] == 1:
          no_of_inv = no_of_inv + b + c 
          a++
       else if arr[i] == 2:
          no_of_inv = no_of_inv + c
          b++
       else:
          c++

Answer 2

( , ).

(i, j) 0 ≤ i < j < n. S[j] (i, j); .. S[j] - A[i] > A[j] 0 ≤ i < j. T = S[0] + S[1] + … + S[n - 1].

C[x][j] - A[i] > x 0 ≤ i < j. S[j] = C[A[j]][j] j. 3n C[x][j] , S .

Python:

>>> import numpy as np
>>> A = np.array([1, 1, 3, 2, 3, 1, 3])
>>> C = {x: np.cumsum(A > x) for x in np.unique(A)}
>>> T = sum(C[A[j]][j] for j in range(len(A)))
>>> print T
4

, asmpytotic terms — C. . , .