数组中的显著逆序对

Question

我正在做一个作业，题目是找出一个整数数组中的“显著逆序对”数量。“显著逆序对”的定义如下：

在一个排列 [a₀, a₁, a₂, ..., a_n] 中，如果存在某个 i < j 使得 a_i > 2 a_j，那么这个对就是一个显著逆序对。例如，对于 a = [4,5,2,1,3]，它恰好有 3 个显著逆序对，因为在这个排列中 a₀ > 2 a₃，a₁ > 2 a₂，a₁ > 2 a₃。

解决这个问题需要时间复杂度为 O(n log n)。这就需要用到分治法。我选择基于归并排序来实现这个解决方案。

我理解这里的分割操作：

def countInversions(list):
    if(len(list) <= 1):
        return list, 0
    else:
        mid = int(len(list)/2)
        left, a = countInversions(list[:mid])
        right, b = countInversions(list[mid:])
        result, c = mergeAndCount(left, right)
        return result, (a + b + c)

但是我在合并和计数的方法上遇到了问题。特别是计算显著逆序对的数量。我是从计算普通逆序对的代码上进行修改的。

def mergeAndCount(left, right):
    result = []
    count = 0
    i,j = 0,0
    while(i < len(left) and j < len(right)):
        if(left[i] > 2*right[j]):
            count += 1
        if(left[i] < right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    while(left[i:] or right[j:]):
        if(left[i:]):
            if(left[i] > 2*right[j-1]):
                count += 1
            result.append(left[i])
            i += 1
        if(right[j:]):
            if(left[i-1] > 2*right[j]):
                count += 1
            result.append(right[j])
            j += 1
    return result, count

所以 print(countInversions([4,5,2,1,3])) 应该返回 3，但它却返回了 1。

我希望能得到一些关于我的合并和计数方法的指导。

---

最终的实现：

def countInversions(list):
    if(len(list) <= 1):
        return list, 0
    else:
        mid = int(len(list)/2)
        left, a = countInversions(list[:mid])
        right, b = countInversions(list[mid:])
        result, c = mergeAndCount(left, right)
        return result, (a + b + c)

def mergeAndCount(left, right):
    result = []
    count = 0
    i,j = 0,0

    while(i < len(left) and j < len(right)):
        if(left[i] > 2*right[j]):
            count += len(left)-i
            j += 1
        else:
            i += 1

    i,j = 0,0
    while(i < len(left) and j < len(right)):
        if(left[i] < right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result, count

Answer 1

你快要完成了，但有两个问题：

1. 当你发现 left[i] > 2*right[i] 时，你应该得出结论，left[i:] 中的所有值都大于 2*right[i]，所以你应该把计数加上 len(left[i:])，这其实就是 len(left) - i。 （你只加了1，所以你的值太低了。）

2. 你需要把合并的过程分成两个阶段，一个是计算重要的逆序对，另一个是生成一个排序后的输出数组。 （在正常的逆序对计数中，这两个过程可以在同一时刻移动 i 和 j，所以可以合并，但在你的情况下并不是这样。）

修正后的代码：

def mergeAndCount(left, right):
    result = []
    count = 0
    i,j = 0,0

    while(i < len(left) and j < len(right)):
        if(left[i] > 2*right[j]):
            count += len(left)-i
            j += 1
        else:
            i += 1

    i,j = 0,0                
    while(i < len(left) and j < len(right)):
        if(left[i] < right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    while(left[i:] or right[j:]):
        if(left[i:]):
            result.append(left[i])
            i += 1
        if(right[j:]):
            result.append(right[j])
            j += 1
    return result, count