algorithm - 为所有索引查找数组中索引右侧的最小元素

Question

给定一个数组，我希望找到 i 处当前元素右侧的最小元素，其中 0=<i<n并将对应的最小元素的索引存储在另一个数组中。

例如，我有一个数组 A ={1,3,6,7,8}结果数组将包含 R={1,2,3,4} 。(R 数组将索引存储到最小元素)。我只能想到 O(N^2) 方法。对于 A 中的每个元素，我将遍历 A 右侧的剩余元素并找到最小值。是否可以在 O(N) 中执行此操作？我想使用该解决方案来解决另一个问题。

Answer 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

这将通过数组一次， 为您提供 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]

您可以看到新数组(第二个)的每个元素的索引都正确指向原始数组(第一个)中每个元素右侧的最小值。

请注意，我对“在……的右边”做了一个具体定义，这意味着它不包括当前元素。如果您定义的“在……的右边”包括当前元素，只需更改循环内 insert 和 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