题目描述
Given two arrays of length m
and n
with digits 0-9
representing two numbers. Create the maximum number of length k <= m + n
from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k
digits.
Note: You should try to optimize your time and space complexity.
Example 1:
Input:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
Output:
[9, 8, 6, 5, 3]
Example 2:
Input:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
Output:
[6, 7, 6, 0, 4]
Example 3:
Input:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
Output:
[9, 8, 9]
题意:给定长度分别为 m
和 n
的两个数组,其元素由 0-9 构成,表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n)
个数字拼接成一个新的数,要求从同一个数组中取出的数字保持其在原数组中的相对顺序。求满足该条件的最大数。结果返回一个表示该最大数的长度为k
的数组。
算法1
(动态规划) $O(nmk)$
这一题很容易想到的一种方法就是使用如下的状态表示:
状态表示:dp[i][j][t]
代表使用nums1
数组前i
个数字和nums2
数组前j
个数字拼成长度为t
的最大数字是多少。
状态转移:在求解dp[i][j][t]
的时候,我们只需要分别考虑是否选用nums
第i
个数和nums2
中第j
个数即可。
dp[i][j][t] = max(dp[i - 1][j][t],max(dp[i][j][t],dp[i - 1][j][t - 1] * 10 + nums1[i - 1]))
dp[i][j][t] = max(dp[i][j - 1][t],max(dp[i][j][t],dp[i][j - 1][t - 1] * 10 + nums2[j - 1]))
状态初始化:全为0即可
答案表示:dp[n][m][k]
,然后将该数值每一位分解出来即可。
时间复杂度为:$O(nmk)$。因为这里需要存储超长整数,我选用的python来实现上述想法。这种解法在Leetcode上可以通过80个测试样例,然后TLE。
class Solution:
def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
n = len(nums1)
m = len(nums2)
if k == 0:
return []
dp = [[[0 for i in range(k + 1)] for i in range(m + 1)] for i in range(n + 1)]
for t in range(1, k + 1):
for i in range(0, n + 1):
for j in range(max(0,t - i),m + 1):
if i > 0:
dp[i][j][t] = max(dp[i - 1][j][t],max(dp[i][j][t],dp[i - 1][j][t - 1] * 10 + nums1[i - 1]))
if j > 0:
dp[i][j][t] = max(dp[i][j - 1][t],max(dp[i][j][t],dp[i][j - 1][t - 1] * 10 + nums2[j - 1]))
ans = dp[n][m][k]
res = []
while ans > 0:
res.append(ans % 10)
ans = ans // 10
res.reverse()
return res
算法2
(贪心/单调栈) $O(k(n + m))$
题解2:我们可以先考虑只从一个数组中选择s
个数凑成的最大值我们应该怎么做呢?我们可以维护一个类似单调栈的一样的数组,我们从前往后遍历整个数组,如果数组不为空,并且当前元素大于当前栈顶元素,并且弹出栈顶元素后不会导致剩下的元素不足s
个,那么我们就弹出栈顶元素,重复上述操作直至条件不成立。如果此时栈内元素小于s
个,那么我们就可以将当前元素加入栈中。这就是我们下面select
函数执行的功能,很明显时间复杂度为$O(n)$
那么我们从两个数组中共选择k
个,那么最多总共有k + 1
种可能,即分别在第一个数组中选择0,1,2,...,k
个元素,剩下的若干个元素在第二个数组中选取。这样的时间复杂度就是$O(k)$。
我们在两个数组中分别挑选出若干个元素后,我们只需要关心如何合并他们使得能够获得最大的值。我们将两个数组元素从前往后依次比较,直至某一个数字大于另一个数组中对应位置上的数组,我们就选取这个数组的头元素加入答案。这里我们利用了vector<int>
中自带的<
运算符完成上述比较,同时我们将数组转化成deque<int>
方便在记录头元素后删除头元素。
最后我们在所有的k + 1
种选择中选取合并后结果最大的那个元素作为答案即可。这里我们同样使用了右值引用和move
函数来避免拷贝引来的开销。
时间复杂度:$O((m + n)k)$
class Solution {
public:
vector<int> select(vector<int> &a,int n,int k)
{
vector<int> res;
for(int i = 0 ; i < n ; i ++)
{
while(!res.empty() && res.back() < a[i] && res.size() + n - i > k)
res.pop_back();
if(res.size() < k) res.push_back(a[i]);
}
return res;
}
vector<int> merge(vector<int> & a,vector<int> & b)
{
vector<int> res;
deque<int> x(a.begin(),a.end());
deque<int> y(b.begin(),b.end());
while(!x.empty() && !y.empty())
{
if(x > y) {res.push_back(x.front());x.pop_front();}
else{res.push_back(y.front());y.pop_front();}
}
while(!x.empty()) {res.push_back(x.front());x.pop_front();}
while(!y.empty()) {res.push_back(y.front());y.pop_front();}
return res;
}
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int n = nums1.size(),m = nums2.size();
vector<int> res(k,0);
for(int s = 0 ; s <= min(k,n) ; s ++)
{
int t = k - s;
if(t > m) continue;
vector<int> ans1 = select(nums1,n,s);
vector<int> ans2 = select(nums2,m,t);
vector<int>&& cur = merge(ans1,ans2);
if(res < cur) res = move(cur);
}
return res;
}
};
deque
比较运算的时间复杂度是线性的,不是 $O(1)$ 的,所以算法2的时间复杂度应该是 $O(k^2(m+n)$ 吧。