算法题目：拼接最大数：
提示：会使用到了贪心算法，题目难度：比较困难。
贪心算法一般按如下步骤进行：
①建立数学模型来描述问题。 ②把求解的问题分成若干个子问题 。 ③对每个子问题求解，得到子问题的局部最优解。 ④把子问题的解局部最优解合成原来解问题的一个解。
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯 。
算法题目描述
给定长度分别为 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]
java解题参考代码
public static void main(String[] args) throws ParseException {
int[] num1 = {3, 9};
int[] num2 = {8, 9};
int k = 3;
int[] i = maxNumber(num1, num2, k);
System.out.println(i);
}
private static int[] maxInNums(int[] nums, int k) {
int[] max = new int[k];
int len = nums.length;
for (int i = 0, j = 0; i < len; ++i) {
while (j > 0 && k - j < len - i && max[j - 1] < nums[i])
--j;
if (j < k)
max[j++] = nums[i];
}
return max;
}
private static boolean greater(int[] nums1Max, int i, int[] nums2Max, int j) {
int lenNums1Max = nums1Max.length;
int lenNums2Max = nums2Max.length;
while (i < lenNums1Max && j < lenNums2Max && nums1Max[i] == nums2Max[j]) {
++i;
++j;
}
return j == lenNums2Max || (i < lenNums1Max && nums1Max[i] > nums2Max[j]);
}
private static int[] merge(int[] nums1Max, int[] nums2Max) {
int lenCurRes = nums1Max.length + nums2Max.length;
int[] curRes = new int[lenCurRes];
for (int i = 0, j = 0, m = 0; m < lenCurRes; ++m) {
curRes[m] = greater(nums1Max, i, nums2Max, j) ? nums1Max[i++] : nums2Max[j++];
}
return curRes;
}
public static int[] maxNumber(int[] nums1, int[] nums2, int k) {
int[] res = null;
for (int i = Math.max(k - nums2.length, 0); i <= Math.min(nums1.length, k); ++i) {
int[] merge = merge(maxInNums(nums1, i), maxInNums(nums2, k - i));
res = (res == null || greater(merge, 0, res, 0)) ? merge : res;
}
return res;
}