0

给定一个数组，我希望找到当前元素右侧的最小元素 i where0=<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

这通过数组一次，给你 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]

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

请注意，我采用了“右侧”的一个特定定义，这意味着它不包括当前元素。如果您对“右侧”的定义包括当前元素，只需更改循环中insertandif语句的顺序，以便首先更新索引：

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 回答