321、拼接最大的数字
给定长度分别为 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]
题解
1、数组的最大子序列+数组归并
- 从所有的情况中选择最优：
- 实现快速查找一个数组的最大子序列
- 实现快速合并并两个数组，并保证序列的字典顺序最大
- 优化时间复杂度
$$
[1…k] = max(\sum_{i=0}^k merge(subsequence(num1,i),subsequence(num2,k-i)))
$$
- 代码
// java
class Solution {
public int[] maxNumber(int[] num1,int[] num2,int k) {
int[] res = null;
int len1 = num1.length;
int len2 = num2.length;
System.out.println("num1: ");
print(num1);
System.out.println("num2: ");
print(num2);
boolean first = true;
for (int i = Math.max(0,k-len2);i <= Math.min(k,len1);i++) {
int[] sub1 = subSequence(num1,i);
System.out.println("sub1-"+i+": ");
print(sub1);
int[] sub2 = subSequence(num2,k-i);
System.out.println("sub2-"+i+": ");
print(sub2);
int[] tmp = merge(sub1,sub2);
System.out.println("tmp: ");
print(tmp);
if (first) {
res = tmp;
first = false;
}else {
res = maxSubSequence(res,tmp)?res:tmp;
}
System.out.println("res: ");
print(res);
}
return res;
}
private int[] subSequence(int[] nums,int k) {
int l = nums.length;
if (l <= k) return nums;
int drop = l - k;
int[] ans = new int[k];
if (k == 0) return ans;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < l; i++) {
while (!stack.empty() && nums[i] > stack.peek() && drop-- > 0) {
stack.pop();
}
stack.push(nums[i]);
}
// 裁剪大小
while (stack.size() > k) stack.pop();
for (int i = k - 1;i >=0 ;i--) {
ans[i] = stack.pop();
}
return ans;
}
private void print(int[] nums) {
for (int item : nums) {
System.out.print(item+" ");
}
System.out.println();
}
// 有问题
private int[] merge(int[] nums1,int[] nums2) {
int l1 = nums1.length;
int l2 = nums2.length;
if(l1==0) return nums2;
if(l2==0) return nums1;
int ans[] = new int[l1+l2];
int i1 = 0;
int i2 = 0;
for(int i=0;i<l1+l2;i++){
if(maxSubSequence(Arrays.copyOfRange(nums1, i1, l1),Arrays.copyOfRange(nums2, i2, l2))){
ans[i] = nums1[i1++];
}
else{
ans[i] = nums2[i2++];
}
}
return ans;
}
// true -> nums1 > nums2
private boolean maxSubSequence(int[] nums1,int[] nums2) {
// 求出长度较小的值
int n = Math.min(nums1.length,nums2.length);
for(int i=0;i < n;i++){
if(nums1[i] > nums2[i]) return true;
else if(nums1[i] < nums2[i]) return false;
else continue;
}
return nums1.length > nums2.length;
}
public static void main(String[] args) {
Leetcode321 leetcode321 = new Leetcode321();
int[] num1 = {3,4,6,5};
int[] num2 = {9, 1, 2, 5, 8, 3};
leetcode321.maxNumber(num1, num2, 5);
System.out.println("-------------------------------");
int[] num3 = {6,7};
int[] num4 = {6,0,4};
leetcode321.maxNumber(num3, num4, 5);
}
}
-
class Solution {
vector<int> nums1;// 队列1
vector<int> nums2;// 队列2
int findMaxIndex(vector<int> &nums, int idx, int len){
int maxIdx = idx;
for (int i = idx; i < nums.size() - len; ++i){
if (nums[i] > nums[maxIdx]){
maxIdx = i;
}
}
return maxIdx;
}
// 重复计算太多，时间复杂度太高
void dfs(vector<int> &rst, int idx1, int idx2, int k){
if (k == 0){
return;
}
int len1 = max(0, k - ((int)nums2.size() - idx2)-1);
int maxIdx1 = findMaxIndex(nums1, idx1, len1);
// printf("idx1 = %d, len1=%d, maxIdx1=%d\n", idx1, len1, maxIdx1);
int len2 = max(0, k - ((int)nums1.size() - idx1)-1);
int maxIdx2 = findMaxIndex(nums2, idx2, len2);
// printf("idx2 = %d, len2=%d, maxIdx2=%d\n", idx2, len2, maxIdx2);
if (maxIdx1 == nums1.size()){
rst.push_back(nums2[maxIdx2]);
return dfs(rst, idx1, maxIdx2 + 1, k-1);
}
else if (maxIdx2 == nums2.size()){
rst.push_back(nums1[maxIdx1]);
return dfs(rst, maxIdx1 + 1, idx2, k-1);
}
else{
if (nums1[maxIdx1] > nums2[maxIdx2]){
rst.push_back(nums1[maxIdx1]);
return dfs(rst, maxIdx1 + 1, idx2, k-1);
}
else if (nums1[maxIdx1] < nums2[maxIdx2]){
rst.push_back(nums2[maxIdx2]);
return dfs(rst, idx1, maxIdx2 + 1, k-1);
}
else {
rst.push_back(nums1[maxIdx1]);
vector<int> rst1, rst2;
rst1 = rst2 = rst;
dfs(rst1, maxIdx1 + 1, idx2, k-1);
dfs(rst2, idx1, maxIdx2 + 1, k-1);
rst = rst1;
for (int i = 0; i < rst1.size(); ++i){
if (rst1[i] > rst2[i]){
break;
}
else if (rst1[i] < rst2[i]){
rst = rst2;
break;
}
}
return;
}
}
}
// 广度优先搜索
void bfs(vector<int> &rst, int k){
set<pair<int, int>> s1;
s1.insert(make_pair(0, 0));
while (k){
int maxNum = -1;
set<pair<int, int>> s2;
for (auto &p : s1){// 遍历s1
int idx1 = p.first;
int idx2 = p.second;
int len1 = max(0, k - ((int)nums2.size() - idx2)-1);
int maxIdx1 = findMaxIndex(nums1, idx1, len1);// 找到最大值的下标
int maxNum1 = maxIdx1 >= nums1.size() ? -1 : nums1[maxIdx1];
// printf("idx1 = %d, len1=%d, maxIdx1=%d, maxNum1=%d\n", idx1, len1, maxIdx1, maxNum1);
if (maxNum1 > maxNum){
s2.clear();
s2.insert(make_pair(maxIdx1 + 1, idx2));
maxNum = maxNum1;
}
else if (maxNum1 == maxNum){
s2.insert(make_pair(maxIdx1 + 1, idx2));
}
int len2 = max(0, k - ((int)nums1.size() - idx1)-1);
int maxIdx2 = findMaxIndex(nums2, idx2, len2);
int maxNum2 = maxIdx2 >= nums2.size() ? -1 : nums2[maxIdx2];
// printf(" idx2 = %d, len2=%d, maxIdx2=%d, maxNum2=%d\n", idx2, len2, maxIdx2, maxNum2);
if (maxNum2 > maxNum){
s2.clear();
s2.insert(make_pair(idx1, maxIdx2 + 1));
maxNum = maxNum2;
}
else if (maxNum2 == maxNum){
s2.insert(make_pair(idx1, maxIdx2 + 1));
}
}
s1.swap(s2);
rst.push_back(maxNum);
--k;
}
}
public:
vector<int> maxNumber(vector<int>& a, vector<int>& b, int k) {
nums1.swap(a);
nums2.swap(b);
vector<int> rst;
//dfs(rst, 0, 0, k);
bfs(rst, k);
return rst;
}
};
// 作者：hareast
// 链接：https://leetcode-cn.com/problems/create-maximum-number/solution/zheng-chang-si-lu-qiu-jie-bfs28-ms-zai-suo-you-cpp/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
vector<int>ans;
const int n1=nums1.size();
const int n2=nums2.size();
// 迭代求最优解
for(int k1=0;k1<=k;++k1)
{
const int k2=k-k1;
if(k1>n1||k2>n2)
continue;
ans=max(ans,maxNumber(maxNumber(nums1,k1),maxNumber(nums2,k2)));
}
return ans;
}
private:
// 求数组nums的大小为k的最大自序列
vector<int>maxNumber(vector<int>&nums, int k)
{
if(k==0) return{};
vector<int>ans;// 利用栈
int to_pop=nums.size()-k;
for(const int num:nums)
{
// 删除小的数字
while(!ans.empty()&&num>ans.back()&&to_pop-->0)
ans.pop_back();
ans.push_back(num);// 添加大的数字或者添加小的数字
}
ans.resize(k);// 重新设置大小
return ans;
}
vector<int>maxNumber(const vector<int>&nums1,const vector<int>&nums2)
{
vector<int>ans;
auto s1=nums1.cbegin();
auto s2=nums2.cbegin();
auto e1=nums1.cend();
auto e2=nums2.cend();
// 合并两个子数组，调用库函数lexicographical_compare
while(s1!=e1||s2!=e2)
ans.push_back(
lexicographical_compare(s1,e1,s2,e2)? *s2++: *s1++);
return ans;
}
};
// 作者：easier
// 链接：https://leetcode-cn.com/problems/create-maximum-number/solution/ba-wen-ti-fen-jie-cheng-zi-wen-ti-qiu-jie-cjie-fa-/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
vector<int> res(k, 0);
int n = nums1.size(), m = nums2.size();
// 假设有最大子序列中有s个元素来自nums1，对所有可能的s值遍历
for (int s=max(0, k-m); s<=min(k, n); s++){
vector<int> temp;
int i = 0, j = 0;
// nums1中长度为s的最大子序列
vector<int> temp1 = maxKsequence(nums1, s);
// nums2中长度为k-s的最大子序列
vector<int> temp2 = maxKsequence(nums2, k-s);
// 对两个子序列进行归并
// lexicographical_compare：比较两个序列的字典序大小
auto iter1 = temp1.begin(), iter2 = temp2.begin();
while (iter1 != temp1.end() || iter2 != temp2.end()){
temp.push_back(lexicographical_compare(iter1, temp1.end(), iter2, temp2.end()) ? *iter2++ : *iter1++);
}
// 如果归并后的最大子序列大于目前已找到的最大子序列，则更新解
res = lexicographical_compare(res.begin(), res.end(), temp.begin(), temp.end()) ? temp : res;
}
return res;
}
// 求数组v的长度为k的最大子序列
vector<int> maxKsequence(vector<int> v, int k){
int n = v.size();
if (n <= k)
return v;
vector<int> res;
int pop = n-k;
for (int i=0; i<n; i++){
while(!res.empty() && v[i]>res.back() && pop-->0)
res.pop_back();
res.push_back(v[i]);
}
res.resize(k);
return res;
}
};
// 作者：Gorilla
// 链接：https://leetcode-cn.com/problems/create-maximum-number/solution/cshou-xian-qiu-jie-zi-wen-ti-zai-he-bing-zi-wen-ti/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- Java实现
class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int m = nums1.length;
int n = nums2.length;
int[] ans = new int[k];
for(int i=Math.max(0,k-n);i<=Math.min(k,m);i++){
int[] seq1 = maxSubSequence(nums1,i); //子序列1
int[] seq2 = maxSubSequence(nums2,k-i); //子序列2
int[] temp = merge(seq1,seq2); //归并
if(compare(temp,ans)){ //比较逻辑大小
// for(int j=0;j<k;j++){
// ans[j] = temp[j];
// }
ans = temp;
}
}
return ans;
}
//求数组中k个顺序不变的最大子序列
private int[] maxSubSequence(int[] nums, int k){
int l = nums.length;
if(l<=k) return nums;
//代表最多可以丢弃几个数
int drop = l-k;
int[] ans = new int[k];
if(k==0) return ans;
Stack<Integer> stack = new Stack<>();
for(int i=0;i<l;i++){
while(!stack.empty() && nums[i]>stack.peek() && drop-->0){
stack.pop();
}
stack.push(nums[i]);
}
//裁剪大小
while(stack.size()>k) stack.pop();
for(int i=k-1;i>=0;i--){
ans[i] = stack.pop();
}
return ans;
}
//归并数组
//这里遇到了好多坑，一开始是想着按照归并排序那种方式归并的，结果发现在遇到连续几位数字相同的情况下时会出现问题
private int[] merge(int[] nums1, int[] nums2){
int l1 = nums1.length;
int l2 = nums2.length;
if(l1==0) return nums2;
if(l2==0) return nums1;
int ans[] = new int[l1+l2];
int i1 = 0;
int i2 = 0;
for(int i=0;i<l1+l2;i++){
if(compare(Arrays.copyOfRange(nums1, i1, l1),Arrays.copyOfRange(nums2, i2, l2))){
ans[i] = nums1[i1++];
}
else{
ans[i] = nums2[i2++];
}
}
return ans;
}
//比较数组的逻辑大小，如果数组长短不一样并且前n个数字完全一样，则认为长度大的那个数组大
//返回值：若nums1>nums2，返回true
private boolean compare(int[] nums1, int[] nums2){
int n = Math.min(nums1.length,nums2.length);
for(int i=0;i<n;i++){
if(nums1[i]>nums2[i]) return true;
else if(nums1[i]<nums2[i]) return false;
else continue;
}
return nums1.length>nums2.length;
}
}
// 作者：nju_yirui
// 链接：https://leetcode-cn.com/problems/create-maximum-number/solution/javajie-fa-by-nju_yirui/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 5ms
class Solution {
private int[] res;
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
res = new int[k];
for(int i = 0; i <= k; i ++)
if(i <= nums1.length && k - i <= nums2.length)
// 获取最大的子序列并合并
merge(getMax(nums1, i), getMax(nums2, k - i));
return res;
}
private void merge(int[] nums1, int[] nums2){
int p = 0, q = 0, r = 0;
boolean flag = false;
while(p < nums1.length || q < nums2.length){
int t = gt(nums1, p, nums2, q) ? nums1[p ++] : nums2[q ++];
if(flag || (!flag && t > res[r])){
res[r] = t;
flag = true;
}
else if(!flag && t < res[r]) return;// 合并是发现结果小雨之间的结果，直接退出
r ++;
}
}
private boolean gt(int[] nums1, int p, int[] nums2, int q){
while(p < nums1.length && q < nums2.length && nums1[p] == nums2[q]){
p ++;
q ++;
}
return q == nums2.length || (p < nums1.length && nums1[p] > nums2[q]);
}
private int[] getMax(int[] nums, int k){
int[] res = new int[k];
if(k == 0) return res;
int n = nums.length, size = 0;
for(int i = 0; i < n; i ++){
// 用数组模拟栈
while(size > 0 && n - i > k - size && nums[i] > res[size - 1])
size --;
if(size < k) res[size ++] = nums[i];
}
return res;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
