0

このエラーを克服するのに苦労しています。マージソートでのマージに似たルーチンを実行しています。多分私は何か間違ったことをインスタンス化しています。コードは次のとおりです。

def MergeAndCountSplitInv(arr, length):
    left = arr[0:length/2]
    right = arr[length/2+1: length]

    i = 0
    j = 0
    numSplitInv = 0
    newArray = [0] * length
    for k in range(len(arr)):
        if (left[i] < right[j]):
            #newArray.insert(k, left[i])
            newArray.append(left[i])
            i = i + 1
        else: #(right[j] < left[i]
            #newArray[k].insert(k, right[j])
            newArray.append(right[j])
            j = j + 1
            numSplitInv = numSplitInv + (length/2 - i)

    return ReturnValue(newArray, numSplitInv)

エラーは次のように与えられます。

File "InversionCount.py", line 31, in MergeAndCountSplitInv if (left[i] < right[j]): IndexError: list index out of range

助けてくれてありがとう

4

3 に答える 3

3

問題の 1 つは、スライス インデックスの理解です。これらの 2 行:

left = arr[0:length/2]
right = arr[length/2+1: length]

次のように変更する必要があります。

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

開始インデックスが含まれており、終了インデックスはスライスに含まれていない最初の要素であるため、完全なパーティションを取得するには、右側の開始と同じインデックスを左側の終了に使用します。

しかし、本当の問題は、 orの終わりから離れたかどうかを確認せずにiandをインクリメントすることです。そのため、最終的にはインデックス エラーが発生します。jleftright

于 2012-07-17T03:01:04.247 に答える
1

リスト内のすべての要素を既に消費しているかどうかを確認するのを忘れていました。

于 2012-07-17T03:01:15.817 に答える
1

問題をもう少し明確にするために、リストが次のようになるかどうかを考えてみてください。

right = [1, 2, 3, 4]
left = [5, 6, 7, 8]

right次に、 -の最後に到達する前にすべてを追加しますが、 - が表示されるエラーが発生するleftかどうかを確認しようとします。right[5] < left[0]リストのいずれかが使い果たされたときのチェックを追加する必要があります-次のようなものです:

if i >= len(right):
   newArray.extend(left)
   break

ケースについても同様ですj >= len(left)。

于 2012-07-17T03:02:28.210 に答える