算法练习--有序列表合并和无序列表合并

有序列表合并

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
# -*- coding: utf-8 -*-
'''
File Name: test.py
Author: liangyou.qiao
mail: liangyou.qiao@shuyun.com
Created Time: 三 6/15 08:13:55 2016
'''
def merge(l1,l2):
lis = []
while len(l1) > 0 and len(l2) >0:
if l1[0] > l2[0]:
lis.append(l2[0])
del(l2[0])
else:
lis.append(l1[0])
del(l1[0])
lis.extend(l1)
lis.extend(l2)
return lis
lis_1 = [1,2,4,6,7,23,233,2231]
lis_2 = [4,5,6,7,10,11,223,333,444,555,556]
print merge(lis_1,lis_2)

关于无序列表合进行有序合并

想到的方案,只有先去排序,在合并

之前想到一种方案,就是使用最小堆去做,但是没有成功,代码也贴出

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
# -*- coding: utf-8 -*-
'''
File Name: 无序列表合并.py
Author: liangyou.qiao
mail: liangyou.qiao@shuyun.com
Created Time: 三 6/15 08:46:54 2016
'''
'''
有待考证,不成立
'''
lis_1 = [2,33,2,111,3,4,5,55,222,2223,33]
lis_2 = [10,22,11,23,44,556,2,1,3,4,11,222,333]
import heapq
def no_merge(lis_1,lis_2):
heapq.heapify(lis_1)
heapq.heapify(lis_2)
lis = []
while len(lis_1) > 0 and len(lis_2) > 0:
if lis_1[0] > lis_2[0]:
num = heapq.heappop(lis_2)
lis.append(num)
else:
num = heapq.heappop(lis_1)
lis.append(num)
if len(lis_1) >0:
lis+ sorted(lis_2)
if len(lis_2) >0:
lis + sorted(lis_2)
return lis
print no_merge(lis_1,lis_2)