algorithm - 具有给定反转的子阵列数

Question

我最近在编程竞赛中未能解决以下问题 -

给定一个包含 n 个值的数组 ar[]，您需要找到包含大于或等于 k 的子数组的数量倒置。

数组中的反转数定义为索引对的数量(i,j)

1 <= i < j <= n and ar[i] > ar[j].

O(nlogn) 的最坏情况复杂度是预期的。

Answer 1

你可以在 O(N log N) 时间内完成:

定义 (i,j) 为最小子数组如果在 ar[i]...ar[j] 中至少有 K 个反转，并且在任何更短的子数组中少于 K 个反转从 i 开始，即，如果您删除一个最小子数组末尾的元素，那么它的反转次数将少于 K。

如果 (i,j) 是一个最小子数组，那么恰好有 N+1-j 个子数组至少有 K 个反转从位置 i 开始，因为向末尾添加元素永远不会减少反转的数量。此外，如果有任何从 i 开始的具有 >= K 个反转的子数组，那么恰好有 一个 从 i 开始的最小子数组。

所以我们要做的就是找到每个位置的最小子数组(如果存在)，然后将相应的子数组总数相加，如下所示(伪代码):

let total=0;
let i,j=1,1;
while(i<=N)
{
    while (j<i || inversions in ar[i]...ar[j] < K)
    {
        ++j;
        if (j>N)
        {
            return total; //out of subarrays
        }
    }
    // (i,j) is now a minimal subarray
    total+=N+1-j

    ++i; //next start position

    //now, IF (i,j) has enough inversions, then it is STILL
    //minimal, because otherwise the previous subarray would not have
    //been minimal either
}

为了满足我们的总复杂度目标，我们需要 ar[i]...ar[j] 中的反转 检查每次迭代最多花费 O(log N)。

我们可以通过将子数组元素保存在平衡搜索树中来做到这一点，每个节点都有一个计数，该计数会记住该节点子树的总大小。当 J 从 1 增加到 N 时，我们将最多向这棵树添加 N 个元素，总成本为 O(N log N)。当 i 从 1 增加到 N 时，我们将从这棵树中删除最多 N 个元素，总成本为 O(N log N)。

此外，当我们向树中添加一个元素时，子数组中的反转次数增加的元素数大于我们添加的元素数，因为新元素位于子数组的末尾。当我们从子数组的开头删除一个元素时，反转次数减少的元素数量少于我们添加的元素数量。这两个数字都需要 O(log N) 来确定，因此我们可以在 O(N log N) 时间内跟踪子数组中的反转总数。