题目描述
给定长度分别为 m
和 n
的两个数组,其元素由 0-9
构成,表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n)
个数字拼接成一个新的数,要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为 k
的数组。
说明: 请尽可能地优化你算法的时间和空间复杂度。
样例
输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:
[9, 8, 6, 5, 3]
输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]
输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]
算法
(贪心) $O(k^2(n + m))$
- 我们考虑枚举每一部分选出数字的个数。
- 假设第一个数组选出
s1
个数,第二个数组选出k - s1
个数,然后我们将其贪心的合并,最后找到最大的。 - 从一个数组选出若干个数使其字典序最大可以通过贪心的做法:如果当前数字比结果数组的末尾大,且移除掉当前的末尾不会导致数字不足 $k$ 个,则移除末尾,直到结果数组为空或者不比结果数组的末尾大。然后当前数字放到末尾。这有些类似于单调栈的更新操作,只不过增加了一个新的弹栈限制。
- 合并时,我们同样采用贪心和暴力的方式,我们比较当前两个数组的大小,然后将较大数组的头元素取出,放入结果数组内,再进行下一次的比较。
时间复杂度
- 枚举
s1
的时间复杂度为 $O(k)$,贪心找字典序最大需要 $O(k + n + m)$ 的时间,合并需要 $O(k(n + m))$ 的时间。 - 故总时间复杂度为 $O(k^2(n + m))$。
空间复杂度
- 需要临时存放每个数组选出字典序最大的子序列,还要存放答案数组,故空间复杂度为 $O(n + m)$。
C++ 代码
class Solution {
public:
vector<int> solve(const vector<int>& nums, int k) {
vector<int> ans(k);
int n = nums.size();
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && n - i - 1 + j >= k && ans[j - 1] < nums[i])
j--;
if (j < k)
ans[j++] = nums[i];
}
return ans;
}
vector<int> merge(const vector<int>& x, const vector<int>& y) {
vector<int> ans;
deque<int> a(x.begin(), x.end());
deque<int> b(y.begin(), y.end());
int n = x.size(), m = y.size();
while (!a.empty() && !b.empty()) {
if (a > b) {
ans.push_back(a.front());
a.pop_front();
} else {
ans.push_back(b.front());
b.pop_front();
}
}
while (!a.empty()) {
ans.push_back(a.front());
a.pop_front();
}
while (!b.empty()) {
ans.push_back(b.front());
b.pop_front();
}
return ans;
}
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int n = nums1.size(), m = nums2.size();
vector<int> ans;
for (int s1 = 0; s1 <= min(n, k); s1++) {
int s2 = k - s1;
if (s2 > m) continue;
vector<int> tmp = merge(solve(nums1, s1), solve(nums2, s2));
if (ans < tmp) ans = tmp;
}
return ans;
}
};
“合并时,我们同样采用贪心和暴力的方式,我们比较当前两个数组的大小,然后将较大数组的头元素取出,放入结果数组内,再进行下一次的比较。”
请问为什么不直接看谁的首元素最大,类似于merge sort的办法?
如果首元素一样大就没办法处理了
任意取一个?
那结果可能就不对了,例如 [6,7,0] 和 [6,7,8] 合并,相同的时候要比较第二位,第二位还相同需要比较第三位,以此类推