数逆序对问题

不滥用感谢。

数逆序对问题

问题描述

给出一个字符串数组，如果（按照字典序）一个大的字符串在比它小的字符串前面我们称这两个字符串组成一个“逆序对”。你需要找到所有的逆序对的个数。经典解法基于MergeSort，有时间复杂度为 $O(n\log n)$ , 空间复杂度 $O(n)$ 的解. 但是我们能不能空间改进到 $O(1)$ ，但是仍然高效地解决问题呢？

输入

第一行是数组大小，第二行是以空格分隔的字符串数组.

输出

所有的逆序对个数.

样例输入

3
aaaaaaaaaa cccccccccc bbbbbbbbbb

样例输出

1

算法思想

设n为问题规模，对于内存空间有限制的情况下，我们可以在子问题的合并步骤时对子序列快速排序，在时间复杂度保持多项式指数不变的情况下, 只使用 $O(1)$ 的空间完成问题的求解.

算法伪代码如下：

算法复杂度分析：子问题规模为原问题的一半，在子问题求解完成后，合并时需要利用快速排序计算跨越两部分的逆序对个数，复杂度为 $O(n\log n)$ , 所以递归式为:

$T(n) = 2T(n/2) + n\log n$

利用Smart Guess + Prove的方法可知算法的复杂度为 $O(n\log^2n)$ . 由于算法没有使用辅助空间，算法的空间复杂度为 $O(1)$ .

编辑于 2018-07-22

数逆序对问题

数逆序对问题