create-maximum-number

发表于 | 分类于 ， | 阅读次数 | 
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 Solution(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):
            # nums1中选取x个，k>len2时，至少选取k-len2个
            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]