forked from lilianweng/LeetcodePython
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmerge_lists.py
More file actions
87 lines (75 loc) · 2.44 KB
/
merge_lists.py
File metadata and controls
87 lines (75 loc) · 2.44 KB
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#!/usr/bin/env python
from __future__ import division
import random
'''
Leetcode: Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. '''
# O(n+m)
def merge_two(A, B):
merged = []
m = len(A); n = len(B)
i = j = -1
while True:
if (j >= n-1) or (i+1 <= m-1 and A[i+1] <= B[j+1]):
# go one step on list A
i += 1
merged.append(A[i])
else:
j += 1
merged.append(B[j])
if i == m-1 and j == n-1:
break
print A, B, '-->', merged
return merged
'''
Leetcode: Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. '''
# O(kn)
def merge_k(Ls):
merged = []
k = len(Ls)
frontiers = dict((i, -1) for i in range(k))
final_length = sum([len(l) for l in Ls])
print 'final length:', final_length
while True:
next = None
for i in range(k):
j = frontiers[i]
if j >= len(Ls[i])-1: continue # has reached the last element
if (next is None) or (Ls[i][j+1] < Ls[next][frontiers[next]+1]):
next = i
frontiers[next] += 1
merged.append( Ls[next][frontiers[next]] )
if len(merged) == final_length: break
print Ls, '-->', merged
return merged
'''
Leetcode: Merge Sorted Array
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note: You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively. '''
def merge_two_into_one(A, B):
merged = []
m = len(A); n = len(B)
A += [0]*n
while n > 0:
if m <= 0 or A[m-1] < B[n-1]:
n -= 1
A[n+m] = B[n]
else:
m -= 1
A[n+m] = A[m]
print B, 'merged into:', A
return merged
if __name__ == '__main__':
merge_two([1,3,5,7], [2,3,4,5,6,7])
merge_two([4,5,6,7,8,9,10], [1,2,3])
merge_two([1,1,1,1], [2,2,2,2])
merge_two([0],[0,0])
print
merge_k([[1,3,5,7], [2,3,4,5,6,7], [4,5,6,7,8,9,10], [1,2,3]])
merge_k([[1,1,1,1], [2,2,2,2],[0],[0,0],[-1,2,3]])
print
merge_two_into_one([1,3,5,7], [2,3,4,5,6,7])
merge_two_into_one([4,5,6,7,8,9,10], [1,2,3])
merge_two_into_one([1,1,1,1], [2,2,2,2])
merge_two_into_one([0],[0,0])