在 C++ 中创建最大数
c++server side programmingprogramming更新于 2024/11/7 20:27:00
假设我们有两个长度分别为 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 := size of nums1, m := size of nums2
- 当 (i < n or j < m) 时，执行 −
- 如果调用函数 greater(nums1, nums2, i, j) 为真，则 −
- 插入nums1[i] 位于 ret 的末尾
- (将 i 增加 1)
- 否则
- 将 nums2[j] 插入 ret 的末尾
- (将 j 增加 1)
- 如果调用函数 greater(nums1, nums2, i, j) 为真，则 −
- 返回 ret
- 定义一个函数modify()，它将接受一个数组v，k，
- 定义一个堆栈st
- 定义一个数组ret
- 初始化i := 0，当i < v的大小时，更新(将i增加1)，执行−
- x := v[i]
- 当(st不为空且st的顶部元素< x且st的大小+v的大小– i – 1 >= k)时，执行−
- 从st中删除元素
- 如果st的大小< k，则−
- 将x插入st
- 当(st 不为空)时，执行 −
- 在 ret 末尾插入 st 的顶部元素
- 从 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] > 时返回 true b[j]
- 从 main 方法执行以下操作:
- 定义一个数组 ret
- n := nums1 的大小
- m := nums2 的大小
- 初始化 i := 0，当 i <= k 时，更新(将 i 增加 1)，执行 −
- 如果 i <= n 且 (k - i) <= m，则 −
- 定义一个数组 candidates = mergeThem(modify(nums1, i), modified(nums2, k - i))
- 如果 greater(candidate, ret, 0, 0) 为真，则 −
- ret := candidates
- 如果 i <= n 且 (k - i) <= m，则 −
- return 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, ]
