How to make this arrays combination algorithm more efficient?

user_12200276 0
Viewed 105

So far I have a for loop that goes through a, then another for loop that checks with values of b, and then takes the highest values of c and places that into the new array


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]

Here you can see we got 25 twice, and we had to loop through the entirety of b more than once, to find the highest value in c to find it.

As you can see I would be looping for every value of a with every value of b again and again (especially when the 3 array sizes increase), what direction should I take?

Edit - larger sample

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]
pseudocode dynamic arrays algorithm performance
2 Answers

You could associate every element of B with its matching element in C, then sort the combined A & B by value.

I.e.,

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) ]

Then in processing this, you take the max of the matching elements in C and associate them with elements of A when you reach them.

(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.

Final answer: [25,3,25]

Running time: O(n log n)

user_20410770

I am not sure of this logic, but it at least works for the sample test(s).

I stored B and C elements as suggested by @Dave as pairs and sorted the list in descending order of C values.

Now, I did something like: for each element (ci, bi), find all elements in A such that aj > bi. Mark jth position as visited (to prevent re-assigning other ci later) and store ci at jth index in output array.

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)
user_46883210
Related