数组的倒置计数表示——数组离排序有多远(或接近)。如果数组已经排序，则反转计数为 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
最佳答案
是的。只需取 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++
关于algorithm - 计算数组中的反转 - 特例，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37229703/