-
Notifications
You must be signed in to change notification settings - Fork 0
/
Merge_k_Arrays.py
30 lines (26 loc) · 1.11 KB
/
Merge_k_Arrays.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#Merge k arrays
#Unoptimized for readibility, performance and use
def merge_k_arrays(*arrays):
#Time Complexity = O(k*n), where k = No of arrays, and n = total number of elements in all the arrays.
indices = [0 for x in range(len(arrays))]
minval = None
size = sum([len(array) for array in arrays])
final_array = []
for index in range(size):
for k in range(len(arrays)):
if indices[k] < len(arrays[k]):
if minval is None:
minval = (k, arrays[k][indices[k]])
else:
if arrays[k][indices[k]] < minval[1]:
minval = (k, arrays[k][indices[k]])
final_array.append(minval[1])
indices[minval[0]] += 1
minval = None
return final_array
print(merge_k_arrays([1, 3, 5, 7], [2, 4, 6], [1, 5, 9], [2, 8, 12], [11, 12, 13, 14]))
#TODO
#Update minval to a dictionary and rename for better readibility.
#Rename k in loop to smth meaningful.
#Analysis
#Seems very inefficient. Maybe better to merge two arrays at a time and keep combining them like that. Might reduce to O(n*logk)