数组中的显著反转

Question

我正在研究一个家庭作业问题，以查找整数数组中有效反转的数量。“显著反转”定义如下：

置换[a₀，a₁，a₂，...，a_n]是其中a_i

解决方案需要具有O（n logn）复杂度。这需要使用分而治之的方法。我选择实现基于合并排序的解决方案。

我理解这里给出的拆分操作：

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

您几乎就要成功了，但是还有两个问题:

>

当您找到左[i]的时

您需要将合并过程分为两个阶段，一个用于计算有效反转，另一个用于生成排序输出数组。（在正常反转计数中，这两个将在同一点移动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