如何让这个数组组合算法更高效？

Question

到目前为止，我有一个遍历 a 的 for 循环，然后是另一个检查 b 值的 for 循环，然后取 c 的最高值并将其放入新数组


D = [0, 0, 0]
for i in A
    highestToAdd = 0
    for j in B
        if B[j] < A[i]
            if C[j] > highestToAdd 
                highestToAdd = C[j]
    D[i] = highestToAdd
return D

input arrays:
A = [3, 1, 7]
B = [5, 0, 2] 
C = [5, 3, 25]

output array is:
D = [25, 3, 25]

在这里你可以看到我们得到了 25 两次，我们不得不不止一次地遍历整个 b 来找到 c 中的最大值。

如您所见，我会一次又一次地用 b 的每个值循环遍历 a 的每个值（尤其是当 3 个数组大小增加时），我应该采取什么方向？

编辑 - 更大样本

A = [5, 2, 1, 9, 3, 1, 5, 4, 2, 2]
B = [8, 1, 7, 10, 6, 2, 5, 2, 4, 3]
C = [9, 5, 8, 4, 6, 10, 3, 9, 6, 8]

would result in
D = [10, 10, 5, 10, 10, 5, 10, 10, 10, 10]

Answer 1

您可以将 B 的每个元素与其在 C 中的匹配元素相关联，然后按值对组合的 A 和 B 进行排序。

即

A = [3, 1, 7]
B = [5, 0, 2]
C = [5, 3, 25]
sorted = [(0,B,3), (1,A), (2,B,25), (3,A), (5,B,5), (7,A) ]

然后在处理这个过程中，取 C 中匹配元素的最大值，并在到达它们时将它们与 A 中的元素相关联。

(0,B,3): max = 3
(1,A): A.1 is associated with 3
(2,B,25): max = 25
(3,A): A.3 is associated with 25
(5,B,5): max = 25
(7,A): A.7 is associated with 25.

最终答案：[25,3,25]

运行时间：O(n log n)

Answer 2

我不确定这个逻辑，但它至少适用于示例测试。

我按照@Dave 的建议将 B 和 C 元素成对存储，并按 C 值的降序对列表进行排序。

现在，我做了类似的事情：对于每个元素 (ci, bi)，找到 A 中满足 aj > bi 的所有元素。将第 j 个位置标记为已访问（以防止稍后重新分配其他 ci）并将 ci 存储在输出数组的第 j 个索引处。

A = [3, 1, 7]
B = [5, 0, 2]
C = [5, 3, 25]
E = []
for i in range(len(C)):
    E.append((C[i], B[i]))

E.sort(reverse = True)

D = {}
visited = [False] * len(B)
for c, b in E:
    ind = 0
    for a in A:
        if not visited[ind] and a >= b:
            D[ind] = c
            visited[ind] = True
        ind += 1

print(D)

如何让这个数组组合算法更高效？

How to make this arrays combination algorithm more efficient?

arrays

algorithm

performance

dynamic

pseudocode