在一个数组中找到无序对的数量

Question

我遇到了一个有趣的算法问题：

给定一个整数数组，找出该数组中的无序对数量，例如对于{1, 3, 2}，答案为1，因为{3, 2}是无序的；对于数组{3, 2, 1}，答案为3，因为{3, 2}，{3, 1}，{2, 1}都是无序的。

显然，这个问题可以通过O(n^2)的暴力解法或枚举所有可能的对并消除那些无效对来解决。

我的问题是，是否有更好的解决方案，因为它看起来像是一个动态规划问题。提供代码片段会很有帮助。

- Mighty_L

---

不，它可能是像{1, 99, 4}这样的东西。但是，我认为你可以假设该数组中没有重复项。 - Mighty_L

Answer 1

使用平衡二叉搜索树可以在 O(n log n) 时间内解决此问题。以下是该算法的伪代码:

tree = an empty balanced binary search tree
answer = 0
for each element in the array:
     answer += number of the elements in the tree greater then this element
     add this element to the tree

- kraskevich

---

你好，请简要解释一下为什么这是 O(n log n) 的吗？我不太擅长复杂度分析，但从我的理解来看，一个单独的 for-loop 意味着 O(n)。 - Alexandru Severin

将元素添加到平衡二叉搜索树中的时间复杂度为O(log n)。对于计算大于给定元素的数量，同样适用。因此，总时间复杂度为O(n * log n)（即每次迭代需要O(log n)的时间）。 - kraskevich

Answer 2

如果你只是想知道无序对的数量，且数组按升序排序。你可以使用这个公式 n * (n - 1) / 2。 假设你的数组有 n 个元素，比如在你的例子中有3个。那么它将是 3 * 2 / 2 = 3。假设没有重复的元素。

- Chiranjivee Thakur

Answer 3

你可以使用修改后的归并排序算法来计算逆序对的数量。窍门在于，在合并两个已排序的子数组时，你可以知道哪些元素不在正确位置上。 如果右子数组中有任何需要排在左子数组前面的元素，则它们就是逆序对。 我已经用Python编写了这段代码。你可以查看下面的解释以获得更好的理解。如果你不理解归并排序，我建议你重新学习一遍，然后这将更加直观易懂。

def merge_sort(l):
    if len(l) <= 1:
        return (0, l)
    else:
        mid = len(l) / 2
        count_left, ll = merge_sort(l[0:mid])
        count_right, lr = merge_sort(l[mid:])
        count_merge, merged = merge(ll, lr)
        total = count_left + count_right + count_merge
        return total, merged

def merge(left, right):
    li, ri = 0, 0
    merged = []        
    count = 0
    while li < len(left) and ri < len(right):
        if left[li] < right[ri]:
            merged.append(left[li])
            li += 1
        else:
            count += 1
            merged.append(right[ri])
            ri += 1

    if li < len(left):
        merged.extend(left[li:])
    elif ri < len(right):
        merged.extend(right[ri:])
    return count, merged

if __name__ == '__main__':
    # example 
    l = [6, 1 , 2, 3, 4, 5]
    print 'inverse pair count is %s'%merge_sort(l)[0]

• 归并排序的运行时间为 n * log(n)。
• 对于传递的列表 l，merge_sort 返回一个元组（形式为（逆序对数，列表）），其中包含逆序对数量和已排序的列表。
• 合并步骤计算逆序对的数量并将其存储在变量 count 中。

- Bunny Rabbit

Answer 4

这是我做练习试卷时遇到的问题，我认为嵌套的for循环可以很好地解决它。

public static void main(String args[])
{
    int IA[] = {6,2,9,5,8,7};

    int cntr = 0;

    for(int i = 0; i <= IA.length-1;i++)
    {
        for(int j = i; j <= IA.length-1; j++)
        {
            if(IA[i]>IA[j])
            {

                System.out.print("("+IA[i]+","+ IA[j]+")"+";");
                cntr++;
            }

        }
    }

    System.out.println(cntr);

}

- CanoodleDaNoodle

Answer 5

你可以使用修改过的归并排序算法。合并操作看起来会像这样。

merge(a, b):
    i = 0
    j = 0
    c = new int[a.length+b.length]
    inversions = 0
    for(k = 0 ; k < Math.min(a.length, b.length); k++)
        if(a[i] > b[j]):
            inversions++
            c[k] = b[j]
            j++
        else:
            c[k] = a[i]
            i++
    //dump the rest of the longer array in c
    return inversions

合并操作的时间复杂度为O(n)。整个归并排序的时间复杂度为O(n log n)。

- turingcomplete

---

在这种情况下，为什么需要c变量？ - Soravux

你正在将两个已排序的数组合并成一个数组。因此，你需要分配一个足够大的第三个数组来容纳这两个较小数组的元素。换句话说，第三个数组的大小应该是两个较小数组的总和。虽然有一些不需要额外数组的替代实现方法，但我发现这种实现方法简单易懂，可以说明使用归并排序来计算无序对数量的思想。 - turingcomplete

在这种情况下，你不应该同时返回 c 和 inversions 吗？否则，split 函数（调用 merge）不会收敛，对吧？ - Soravux