Как сделать этот алгоритм объединения массивов более эффективным? - PullRequest
Новая
       26

Как сделать этот алгоритм объединения массивов более эффективным?

2 голосов
/ 11 октября 2019

Пока у меня есть цикл for, который проходит через a, затем другой цикл for, который проверяет значения b, а затем принимает самые высокие значения 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, чтобы найти его.

Как вы можете видеть, я быциклы для каждого значения a с каждым значением b снова и снова (особенно, когда 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]

Ответы [ 2 ]

1 голос
/ 11 октября 2019

Я не уверен в этой логике, но она, по крайней мере, работает для тестовых тестов.

Я сохранил B и C элементы, как предложено @Dave, как пары и отсортировалсписок в порядке убывания C значений.

Теперь я сделал что-то вроде: для каждого элемента (ci, bi) найдите все элементы в A, такие что aj > bi. Пометить j th-ю позицию как посещенную (чтобы предотвратить переназначение других 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)
1 голос
/ 11 октября 2019

Вы можете связать каждый элемент 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)

...