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
87
88
89
90
91
92
93
94
95
96
97
98
99
|
"""
https://leetcode.com/problems/create-maximum-number/
"""
class (object):
def maxNumber(self, nums1, nums2, k):
"""
:type nums1: List[int]
:type nums2: List[int]
:type k: int
:rtype: List[int]
"""
def getMax(nums, t):
ans = []
size = len(nums)
for x in range(size):
while ans and len(ans) + size - x > t and ans[-1] < nums[x]:
ans.pop()
if len(ans) < t:
ans.append(nums[x])
return ans
def merge2(nums1, nums2):
ans = []
while nums1 or nums2:
if nums1 > nums2:
ans.append(nums1[0])
nums1 = nums1[1:]
else:
ans.append(nums2[0])
nums2 = nums2[1:]
return ans
def merge(nums1, nums2):
if len(nums1) == 0:
return nums2
if len(nums2) == 0:
return nums1
ans = []
i, j = 0, 0
while True:
if nums1[i:] > nums2[j:]:
ans.append(nums1[i])
i += 1
else:
ans.append(nums2[j])
j += 1
if i == len(nums1):
ans.extend(nums2[j:])
break
if j == len(nums2):
ans.extend(nums1[i:])
break
return ans
len1, len2 = len(nums1), len(nums2)
res = []
for x in range(max(0, k - len2), min(k, len1) + 1):
tmp = merge(getMax(nums1, x), getMax(nums2, k - x))
res = max(tmp, res)
return res
if __name__ == '__main__':
s = Solution()
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
assert s.maxNumber(nums1, nums2, k) == [9, 8, 6, 5, 3]
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
assert s.maxNumber(nums1, nums2, k) == [6, 7, 6, 0, 4]
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
assert s.maxNumber(nums1, nums2, k) == [9, 8, 9]
nums1 = [8,6,9]
nums2 = [1,7,5]
k = 3
assert s.maxNumber(nums1, nums2, k) == [9, 7, 5]
nums1 = [6,6,8]
nums2 = [5,0,9]
k = 3
assert s.maxNumber(nums1, nums2, k) == [9, 6, 8]
nums1 = [9, 9]
nums2 = [8, 7, 6,5,4]
k = 5
assert s.maxNumber(nums1, nums2, k) == [9, 9, 8, 7, 6]
nums1 = [8,9]
nums2 = [3,9]
k = 3
assert s.maxNumber(nums1, nums2, k) == [9, 8, 9]
nums1 = [2,5,6,4,4,0]
nums2 = [7,3,8,0,6,5,7,6,2]
k = 15
assert s.maxNumber(nums1, nums2, k) == [7,3,8,2,5,6,4,4,0,6,5,7,6,2,0]
|
近期评论