使用类似冒泡排序的算法，计算排序前k个最小元素所需的交换次数。

Question

使用类似冒泡排序的算法，计算排序前k个最小元素所需的交换次数。

6

给定一个数组a和整数k，某人使用以下算法获取前k个最小元素：

cnt = 0
for i in [1, k]:
    for j in [i + 1, n]:
        if a[i] > a[j]:
            swap(a[i], a[j])
            cnt = cnt + 1

问题是：如何在时间复杂度小于O(n log n) 的情况下计算 cnt 的值（即在得到最终的k排序数组时需要进行的交换次数），也就是使用上述算法来对前k小的数字进行排序所需的交换次数。

简单地说，就是计算使用上述算法对前k个最小数进行排序所需的交换次数，时间复杂度要小于O(n log n)。

我考虑过使用二叉搜索树，但是我有些困惑（当i增加时，数组会如何变化？如何计算一个固定的i所需的交换次数？ ...）。

- make_lover

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nevets · Accepted Answer

这是一个非常好的问题: 它涉及到逆序对、堆栈和一些证明技巧。

注1: 以下所有索引均为基于1的索引，而不是传统的基于0的索引。

注2: 如果您想直接查看算法，请从底部开始阅读。

首先我们定义逆序对为:

对于a[i]和a[j]，其中ia[j]，那么a[i]和a[j]被称为逆序对。

例如，在下面的数组中:

3 2 1 5 4

a[1]和a[2]是一对逆序对，a[2]和a[3]是另一对逆序对。

在开始分析之前，让我们定义一个共同的语言：在本文中，“以i为起点的逆序对”指的是涉及a[i]的逆序对总数。

例如，对于a = {3, 1, 2}，以1为起点的逆序对为2，以2为起点的逆序对为0。

现在让我们来看一些事实：

如果我们有 i < j < k，且 a[i] > a[k]，a[j] > a[k]，则将 a[i] 和 a[j] 交换（如果它们是逆序对）不会影响从 j 开始的逆序对的总数；
以 A 为数组，并给出两个数字 a 和 b 作为 A 的头元素，如果我们可以使用 a 形成更多的逆序对而不是 b，则我们有 a > b；
从 i 开始的逆序对的总数可能会在交换后发生改变（例如，假设我们有 a = {5, 3, 4}，在将 a[1] 与 a[2] 交换之前，从 1 开始的逆序对的总数为 2，但交换后数组变为 a = {3, 5, 4}，从 1 开始的逆序对数量变为 1）；
设以 i 开始的逆序对的总数为 ip[i]，则有：如果 k 是满足 ip[i] > ip[i + k] 的最小数字，则 a[i] > a[i + k]，同时 a[i] < a[i + 1 .. i + k - 1] 必须为真。换句话说，如果 ip[i + k] 是第一个比 ip[i] 小的数字，则 a[i + k] 也是第一个比 a[i] 小的数字；

证明第一点:

根据逆序对的定义，对于所有形成与 a[j] 逆序对的 a[k]，其中 k > j，必须满足 a[k] < a[j]。由于 a[i] 和 a[j] 是一对逆序对，并且提供了 i < j，我们有 a[i] > a[j]。因此，我们有 a[i] > a[j] > a[k]，这表明逆序对关系没有破坏。

证明第三点:

保持为空，因为显而易见。

证明第四点:

首先，很容易看出当i<j时，a[i]>a[j]，我们有ip[i]>=ip[j]+1>ip[j]。然后，它的逆否命题也成立，即当i<j时，ip[i]<=ip[j]，我们有a[i]<=a[j]。

现在回到正题。由于k是满足ip[i] > ip[i + k]的最小数，因此我们有ip[i] <= ip[i + 1 .. i + k - 1]，这表明根据我们刚刚证明的引理，a[i] <= a[i + 1.. i + k - 1]，这也表明在区间[i + 1，i + k - 1]中没有逆序对。因此，ip[i]与从i + k开始但涉及a[i]的逆序对数量相同。给定ip[i + k] < ip[i]，我们知道在[i + k + 1，n]区域内，a[i + k]的逆序对比a[i]少，这表明a[i + k] < a[i]（根据Point 3）。

您可以写下一些序列，并尝试验证或证明它们不正确:P

现在关于算法。

一种朴素的实现需要O(nk)来计算结果，最坏情况下当k = n时会变为O(n^2).

但是，让我们利用上面的事实：

首先，我们使用Fenwick Tree（参见下方的注1）计算ip[i]，这需要O(n log n)来构造和O(n log n)来计算所有已计算出的ip[i]。

接下来，我们需要利用一些事实。因为交换两个数字只影响当前位置的逆序数，而不影响之后的值（点1和2），所以我们不需要担心值改变。此外，由于在[i + 1, n]中最靠右的较小数与ip和a共享相同的索引，因此我们只需要找到第一个ip[j]小于ip[i]的值。如果我们将排序第一个i个元素所需的交换次数定义为f[i]，则有f[i] = f[j] + 1。

但如何快速找到这个“第一个较小的数字”呢？使用栈！这是一个类似问题的帖子：给定数组A，计算B，使B [i]存储在A [i]左侧最接近A [i]且比A [i]小的元素。

简而言之，我们能够以O(n)的时间复杂度完成此操作。

但是，请等一下，该帖子说“向左”，但在我们的情况下是“向右”。解决方案很简单：在我们的情况下向后执行，然后一切都相同:D

因此，总的算法时间复杂度为O(n log n)+ O(n) = O(n log n)。

最后，让我们通过一个例子来说明（@make_lover评论中的简化示例）：

a = {2, 5, 3, 4, 1, 6}，k = 2

首先，让我们获取逆序对：

ip = {1, 3, 1, 1, 0, 0}

为了计算f[i]，我们需要倒序计算（因为需要使用栈技术）：

f[6] = 0, since it's the last one
f[5] = 0, since we could not find any number that is smaller than 0
f[4] = f[5] + 1 = 1, since ip[5] is the first smaller number to the right
f[3] = f[5] + 1 = 1, since ip[5] is the first smaller number to the right
f[2] = f[3] + 1 = 2, since ip[3] is the first smaller number to the right
f[1] = f[5] + 1 = 1, since ip[5] is the first smaller number to the right

因此，ans = f[1] + f[2] = 3 注意1：使用树状数组（二进制索引树）获取逆序对可以在O（N log N）中完成，这里有一篇关于这个主题的帖子，请看一下：）

更新

Aug/20/2014：在我的上一篇文章中发现了一个关键错误（感谢@make_lover），这里是最新的更新。