经典网站欣赏、,网站域名如何管理,十大免费自媒体素材网站,官网站内优化怎么做给定长度分别为 m 和 n 的两个数组#xff0c;其元素由 0-9 构成#xff0c;表示两个自然数各位上的数字。现在从这两个数组中选出 k (k m n) 个数字拼接成一个新的数#xff0c;要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结…给定长度分别为 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]
代码
class Solution {public int[] maxNumber(int[] nums1, int[] nums2, int k) {int mnums1.length,nnums2.length;int[] resnew int[k];int sMath.max(0,k-n),endMath.min(k,m);for(int is;iend;i)//遍历nums1和nums2不同取数情况返回的最大数组返回最大的结果{int[] curmerge(getMaxNumber(nums1, i),getMaxNumber(nums2, k-i));if(comp(cur,0,res,0))rescur;}return res;}public boolean comp(int[] nums1,int p1 ,int[] nums2, int p2) {
//比较两个序列如果前面元素都相同则长度大的较大if(p2nums2.length) return true;if(p1nums1.length) return false;if(nums1[p1]nums2[p2]) return true;if(nums1[p1]nums2[p2]) return false;return comp(nums1, p11, nums2, p21);}public int[] merge(int[] nums1, int[] nums2) {int nnums1.length,mnums2.length;int cur0,p10,p20;int []retnew int[nm];while (p1n||p2m)//合并两个数组{if(comp(nums1,p1,nums2,p2))ret[cur]nums1[p1];else ret[cur]nums2[p2];}return ret;}public int[] getMaxNumber(int[] nums1, int k) {//单调栈找出单个数组的最大排列int nnums1.length,remn-k,top-1;int[] stacknew int[k];for(int i0;in;i){int curnums1[i];while (top0curstack[top]rem0){top--;rem--;}if(topk-1)stack[top]cur;else rem--;//可删除的额度减一当可删除的额度用尽将不能再移除元素为了保证返回数组的长度}return stack;}
}
