假设我们有两个长度为m和n的数组，数字0-9代表两个数字。我们必须从两个数字中创建小于m + n的最大长度k。我们必须记住，必须保留同一数组中数字的相对顺序。我们必须找到k个数字的数组。因此，如果输入像[3,4,7,5]和[9,1,3,5,8,4]，并且k = 5，则答案将是[9,8,7,5,4 ]。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数mergeThem()，它将使用一个数组nums1，一个数组nums2，
定义数组ret
i：= 0，j：= 0，n：= nums1的大小，m：= nums2的大小
而（i <n或j <m），做-
在ret的末尾插入nums2 [j]
（将j增加1）
在ret的末尾插入nums1 [i]
（将i增加1）
如果调用功能Greater(nums1,nums2,i,j)为true，则-
除此以外
返回ret
定义一个函数modify()，它将采用数组v，k，
定义一个堆栈st
定义数组ret
对于初始化i：= 0，当i <v的大小时，更新（将i增加1），执行-
将x插入st
从st删除元素
x：= v [i]
while（st不为空，且st的顶部元素<x，st的大小+ v的大小– i – 1> = k），执行-
如果st <k的大小，则-
而（st不为空），-
在ret的末尾插入st的top元素
从st删除元素
反转数组ret
返回ret
定义一个函数greater()，它将采用数组a，数组b，i，j，
而（i <a的大小，j <b的大小，并且a [i]与b [j]相同），则执行-
将i加1并将j加1
当j == b的大小或i <a的大小且a [i]> b [j]时返回true
从主要方法执行以下操作：
定义数组ret
n：= nums1的大小
m：= nums2的大小
对于初始化i：= 0，当i <= k时，更新（将i增加1），执行-
定义一个候选数组= mergeThem（modify(nums1,i)，Modify(nums2,k-i)）
如果更大（候选，ret，0、0）为真，则-
ret：=候选人
如果i <= n并且(k-i)<= m，则-
返回ret
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> mergeThem(vector<int> nums1, vector<int> nums2)
{
vector<int> ret;
int i = 0;
int j = 0;
int n = nums1.size();
int m = nums2.size();
while (i < n || j < m) {
if (greater(nums1, nums2, i, j)) {
ret.push_back(nums1[i]);
i++;
}
else {
ret.push_back(nums2[j]);
j++;
}
}
return ret;
}
vector<int> modify(vector<int>& v, int k)
{
stack<int> st;
vector<int> ret;
for (int i = 0; i < v.size(); i++) {
int x = v[i];
while (!st.empty() && st.top() < x && st.size() + (v.size() - i) - 1 >= k) {
st.pop();
}
if (st.size() < k)
st.push(x);
}
while (!st.empty()) {
ret.push_back(st.top());
st.pop();
}
reverse(ret.begin(), ret.end());
return ret;
}
bool greater(vector<int>& a, vector<int>& b, int i, int j)
{
while (i < a.size() && j < b.size() && a[i] == b[j])
i++, j++;
return j == b.size() || (i < a.size() && a[i] > b[j]);
}
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k)
{
vector<int> ret;
int n = nums1.size();
int m = nums2.size();
for (int i = 0; i <= k; i++) {
if (i <= n && (k - i) <= m) {
vector<int> candidate = mergeThem(modify(nums1, i), modify(nums2, k - i));
if (greater(candidate, ret, 0, 0)) {
ret = candidate;
}
}
}
return ret;
}
};
main() {
Solution ob;
vector<int> v = { 3, 4, 7, 5 }, v1 = { 9, 1, 3, 5, 8, 4 };
print_vector(ob.maxNumber(v, v1, 5));
}{ 3, 4, 7, 5 }
{ 9, 1, 3, 5, 8, 4 }
5输出结果
[9, 8, 7, 5, 4, ]