algorithm - 计算数组中的反转 - 特例

Question

数组的倒置计数表示——数组离排序有多远(或接近)。如果数组已经排序，则反转计数为 0。如果数组以相反的顺序排序，则反转计数为最大值。形式上来说，如果 a[i] > a[j] 且 i < j，则两个元素 a[i] 和 a[j] 形成一个反转示例:序列2, 4, 1, 3, 5有三个反转(2, 1), (4, 1), (4, 3)。

现在，有多种算法可以在 O(n log n) 中解决这个问题。

有一种特殊情况，数组只有 3 种类型的元素 - 1、2 和 3。现在，是否可以计算 O(n) 中的反转？

例如 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++