python - 数组中的显着反转

Question

我正在做一个家庭作业，找出整数数组中重要倒置的数量。 “显着反转”定义如下:

A significant inversion in a permutation [a₀, a₁, a₂, ..., a_n] is one in which a_i > 2 a_j for some i < j. so for example a = [4,5,2,1,3] has exactly 3 significant inversions, since for this permutation 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