数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在C++中创建最大数
假设我们有两个长度分别为m和n的数组，其中包含代表两个数字的0-9的数字。我们必须从这两个数字的数字中创建一个长度为k的最大数字，该数字小于m+n。我们必须记住，来自同一个数组的数字的相对顺序必须保持不变。我们必须找到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)时，执行：
- 如果调用函数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不为空)时，执行：
- 将st的顶部元素插入到ret的末尾
- 从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]时返回真
- 在主方法中执行以下操作
- 定义一个数组ret
- n := nums1的长度
- m := nums2的长度
- 对于初始化i := 0，当i <= k时，更新(i加1)，执行：
- 如果i <= n且(k - i) <= m，则：
- 定义一个数组candidate = mergeThem(modify(nums1, i), modify(nums2, k - i))
- 如果greater(candidate, ret, 0, 0)为真，则：
- ret := candidate
- 如果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, ]
更新于：2020年6月1日
162 次浏览
广告