python 列表被解释为整数；倒数

Question

获取错误：

File "inversions.py", line 26, in merge
if left[i] < right[j]:
TypeError: 'int' object is not subscriptable

我的归并排序是这样实现的；接受列表及其长度。基本情况是长度为 1 时，我只是 return 列表（不是作为 int，而是作为列表）：

def mergesort(arr, length):
    if length == 1:
        return arr

合并排序函数在非基本情况下的工作：

    n = length // 2
    left = arr[:n]
    right = arr[n:]

    lsort = mergesort(left, len(left))
    rsort = mergesort(right, len(right))
    result = merge(lsort, rsort, length)

    return result

然后是合并两个排序子列表的合并函数，定义如下：

def merge(left, right, length):
    buff = []
    i = j = count = 0

这个合并函数显然是在所有递归调用完成后由合并排序函数调用的。

此合并函数中有 if-else 语句处理它的工作：

    if left[i] < right[j]:
        buff.append(left[i])
        i += 1

        if i == len(left):
            for j in range(j, len(right)):
                buff.append(right[j])
            break

    elif left[i] > right[j]:
        buff.append(right[j])
        j += 1

        count += len(left) - i

        if j == len(right):
            for i in range(i, len(left)):
                buff.append(left[i])
            break

最后，这个合并函数returns 'count';反转次数。

从错误来看，似乎 'left' 等被解释为整数，因此给我下标错误。但我只是不明白为什么它们是整数，而它们显然应该是列表（或者我可能只是遗漏了一些非常明显的东西）。

我实在想不通。任何帮助表示赞赏！ :)

Answer 1

我看过你的代码，在 merge 函数中你正在 returning 类型 int 的变量 count，然后将其传递给 merge 再次作为递归中的数组。所以块 if left[i] < right[j]: 将不起作用。

将 merge 函数更改为 return buff 变量。

python 列表被解释为整数；倒数

python list being interpreted as an integer; counting inversions

python

mergesort

divide-and-conquer

python-3.x