0

配列を指定して、現在の要素の右側にある i where の最小要素を見つけ、0=<i<n対応する最小要素のインデックスを別の配列に格納したいと考えています。

たとえば、配列 A ={1,3,6,7,8} があります。結果の配列には R={1,2,3,4} が含まれます。(R 配列は最小要素へのインデックスを格納します)。私は O(N^2) アプローチしか考えられませんでした.. A の各要素について、残りの要素を A の右側にトラバースし、最小値を見つけます。O（N）でこれを行うことは可能ですか？このソリューションを使用して、別の問題を解決したいと考えています。

4

2 に答える 2

1

次の疑似コードに従って、右側から配列を埋め、現在の最小値のインデックスを維持することにより、O(n) でこれを行うことができるはずです。

def genNewArray (oldArray):
    newArray = new array[oldArray.size]
    saveIndex = -1
    for i = newArray.size - 1 down to 0:
        newArray[i] = saveIndex
        if saveIndex == -1 or oldArray[i] < oldArray[saveIndex]:
            saveIndex = i
    return newArray

これは配列を 1 回通過するため、O(n) 時間の計算量が得られます。これを行うことができるのは、要素 N を超える最小値を見つけたら、要素 N が現在の最小値より小さい場合にのみ要素 N-1 に対して変更されるためです。

次の Python コードは、これを実際に示しています。

def genNewArray (oldArray):
    newArray = []
    saveIndex = -1
    for i in range (len (oldArray) - 1, -1, -1):
        newArray.insert (0, saveIndex)
        if saveIndex == -1 or oldArray[i] < oldArray[saveIndex]:
            saveIndex = i
    return newArray

oldList = [1,3,6,7,8,2,7,4]
x = genNewArray (oldList)

print "idx", [0,1,2,3,4,5,6,7]
print "old", oldList
print "new", x

これの出力は次のとおりです。

idx [0, 1, 2, 3, 4, 5, 6, 7]
old [1, 3, 6, 7, 8, 2, 7, 4]
new [5, 5, 5, 5, 5, 7, 7, -1]

新しい配列 (2 番目の配列) の各要素のインデックスが、元の配列 (最初の配列) の各要素の右側にある最小値を正しく指していることがわかります。

「の右側」の特定の定義を 1 つ取っていることに注意してください。つまり、現在の要素は含まれません。「to the right of」の定義に現在の要素が含まれている場合は、ループ内のinsertandステートメントの順序を変更して、インデックスが最初に更新されるようにします。if

idx [0, 1, 2, 3, 4, 5, 6, 7]
old [1, 3, 6, 7, 8, 2, 7, 4]
new [0, 5, 5, 5, 5, 5, 7, 7]

saveIndex最後の要素の最小インデックスが最後の要素で見つかることがわかっているため、そのコードはチェックを削除します。

def genNewArray (oldArray):
    newArray = []
    saveIndex = len (oldArray) - 1
    for i in range (len (oldArray) - 1, -1, -1):
        if oldArray[i] < oldArray[saveIndex]:
            saveIndex = i
        newArray.insert (0, saveIndex)
    return newArray
于 2013-04-11T01:36:36.483 に答える
0

HWらしい。f(i) は、i の要素の右側にある最小要素のインデックスを示します。ここで、逆方向に歩いて (f(n-1) を入力し、次に f(n-2)、f(n-3)、...、f(3)、f(2)、f(1) を入力)、次のように考えます。 f(i) の情報から f(i-1) の情報がどのように得られるかについて。

于 2013-04-11T01:37:37.423 に答える