LintCode Q552 Create Maximum Number in Python

  • Jinhai ZHOU
  • 4 Minutes
  • 2016年11月6日
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
class Solution:
# @param {int[]} nums1 an integer array of length m with digits 0-9
# @param {int[]} nums2 an integer array of length n with digits 0-9
# @param {int} k an integer and k <= m + n
# @return {int[]} an integer array
def maxNumber(self, nums1, nums2, k):
# Write your code here
# Total Runtime: 1276 ms
# 100% test cases passed.
len_nums1, len_nums2 = len(nums1), len(nums2)
ans = [0]*k
# ans has k numbers
# condition 1: 0 <= i < len_nums1 + 1
# condition 2: 0 <= k - i < len_nums2 + 1
# intersection of 1&2: max(0, k - len_nums2) <= i < min(k + 1, len_nums1 + 1))
for i in xrange(max(0, k - len_nums2), min(k + 1, len_nums1 + 1)):
part1 = self.findMaxSlice(nums1, i) # i < len_nums
part2 = self.findMaxSlice(nums2, k - i)
ans = max(ans, [max(part1, part2).pop(0) for _ in xrange(k)])
return ans
def findMaxSlice(self, nums, len_slice):
len_nums = len(nums) # digits pool
ans = []
for i in xrange(len_nums):
# tested digits len = i, rest digits len = len_nums - i
# need digits len = len_silice - len(ans)
while ans and len_nums - i > len_slice - len(ans) and nums[i] > ans[-1]:
ans.pop()
if len(ans) <= len_slice:
ans.append(nums[i])
return ans
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。