0

可能重复：
计算数组中的反转

给定一个未排序的数组arr，如何计算所有可能的索引(i, j)对arr[i] < arr[j]？复杂度应该是线性的或接近线性的（O(n^2)解决方案很明显）。

编辑：

对不起，我忘了提，但i < j指数的条件。

4

3 回答 3

2

暗示：

对于每对索引 (i, j)，这些陈述中只有一个是正确的：

(a[i]<a[j]), (a[i]=a[j]), (a[i]>a[j]).

您必须遍历数组并计算 a[] 中每个值的实例数

那么，这只是一个组合学的问题......

于 2012-12-09T20:19:18.517 回答
1

[重要]：以下是初始问题的答案，没有条件 i < j

你可以排序O(N * log(N))然后在里面找到答案O(N)，它会给你O(N * log(N))一共。下面是第二部分的代码（数组排序后）：

int count = 0;
int curBefore = 0;
for (int i = 1; i < sorted.Length; i++)
{
    if (sorted[i] > sorted[i - 1])
    {
        curBefore = i;
    }
    count += curBefore;
}

是的，也有一个线性（伪，因为字典操作在一般情况下不是线性的）解决方案！但它需要额外的内存并使用类似字典的数据结构：

int res = sorted.Length * (sorted.Length - 1) / 2;
Dictionary<int, int> dict = new Dictionary<int, int>();
for (int i = 0; i < sorted.Length; i++)
{
    if (!dict.ContainsKey(sorted[i]))
    {
        dict.Add(sorted[i], 0);
    }
    dict[sorted[i]]++;
}
foreach (var pair in dict)
{
    res -= (pair.Value - 1) * pair.Value / 2;
}
于 2012-12-09T20:25:20.333 回答
0

您可以使用自定义的二叉树动态计算此计数。因此，每个节点将包含三个值：节点上的值在(v, lc, ec)哪里，左树上的节点数以及发现等于 的值的数量。如您所见，这些计数器可以在您向树中插入新值时更新。vlcecv

最终答案将保存在全局变量中，并在每次将新值插入树时更新。这个想法是，当一个新的值被插入到树中时，它会经过某个路径，沿着这条路径的节点会确切地知道有多少值小于通过的值，所以在这些节点上最终的答案可以适当更新。

请注意，只有当新值大于当前节点上的值（即，当它将新值转发到右子树时）时，才会更新最终答案 - 这是因为您有额外的约束i < j。

希望这可以帮助！

于 2012-12-09T21:41:14.177 回答