作者:
晚于: 2020-07-22 12:00:00后提交分数乘系数50%
截止日期: 2020-07-29 12:00:00
问题描述 :
给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
说明: 请尽可能地优化你算法的时间和空间复杂度。
示例 1:
输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:
[9, 8, 6, 5, 3]
示例 2:
输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]
示例 3:
输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]
可使用以下main函数：
int main()
{
int m,n,k,data;
vector<int> nums1,nums2;
cin>>m;
for(int i=0; i<m; i++)
{
cin>>data;
nums1.push_back(data);
}
cin>>n;
for(int i=0; i<n; i++)
{
cin>>data;
nums2.push_back(data);
}
cin>>k;
vector<int> res=Solution().maxNumber(nums1,nums2,k);
for(int i=0; i<res.size(); i++)
cout<<res[i];
return 0;
}
输入说明 :
首先输入数组长度m，然后输入m个0-9的数字，各数字以空格分隔。
然后输入数组长度n，然后输入n个0-9的数字，各数字以空格分隔。
最后输入整数k。
输出说明 :
输出结果数组，输出内容无空格。
输入范例 :
输出范例 :
#include <iostream> #include <vector> using namespace std; class Solution { public: vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) { vector<int> ans(k, 0); int n = nums1.size(); int m = nums2.size(); // 假设有最大子序列中有t个元素来自nums1，对所有可能的t值遍历 for(int t=max(0,k-m);t<=min(k,n);t++) { vector<int> temp; vector<int> temp_num1=maxxulie(nums1, t);//num1中长为t的最大子序列 vector<int> temp_num2=maxxulie(nums2, k-t);//num2中长为k-t的最大子序列 auto iter1=temp_num1.begin(); auto iter2=temp_num2.begin(); while(iter1!=temp_num1.end()||iter2!=temp_num2.end()) { // lexicographical_compare：比较两个序列的字典序大小 temp.push_back(lexicographical_compare(iter1,temp_num1.end(),iter2,temp_num2.end())?*iter2++:*iter1++); } // 如果归并后的最大子序列大于目前已找到的最大子序列，则更新解 ans=lexicographical_compare(ans.begin(),ans.end(),temp.begin(),temp.end())?temp:ans; } return ans; } private: // 求数组vc的长度为n的最大子序列 vector<int> maxxulie(vector<int> vc,int n) { int len=vc.size(); if(len<=n) return vc; vector<int> res; int out=len-n; for(int i=0;i<len;i++) { while(!res.empty()&&out&&vc[i]>res.back()) { res.pop_back(); out--; } res.push_back(vc[i]); } res.resize(n);//调整容器的长度大小，使其能容纳n个元素如果n小于容器的当前的size，则删除多出来的元素。否则，添加采用值初始化的元素。 return res; } }; int main() { int m,n,k,data; vector<int> nums1,nums2; cin>>m; for(int i=0; i<m; i++) { cin>>data; nums1.push_back(data); } cin>>n; for(int i=0; i<n; i++) { cin>>data; nums2.push_back(data); } cin>>k; vector<int> res=Solution().maxNumber(nums1,nums2,k); for(int i=0; i<res.size(); i++) cout<<res[i]; return 0; }