LeetCode算法之拼接最大数

https://leetcode-cn.com/problems/create-maximum-number/

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

输入: nums1 = [3, 4, 6, 5] nums2 = [9, 1, 2, 5, 8, 3] k = 5 输出: [9, 8, 6, 5, 3]

这是一道Hard，困难程度超乎想像，代码过于复杂，因此这里分享几个思路。

第一个思路：

根据题意，将两个数组中，取出k位数，按照亿/万/千/百/十/个，组成数字，全部拿出，冒泡获得最大值。这个是最简单的，而且中间过程也可以优化一下。但这是算法，不是纯粹解题，需要考虑时间和空间复杂度，当然也就无法当作最优解。

思路很清晰，但代码编写下来，也不容易，由于不是最优解，也没有写下来的必要性，大家了解就好。

第二个思路：

1、将数字的值、下标和所属数组三个属性，作为一个实体； 2、将两个数组，进行重新组装，并根据值进行倒序排列，得到一个列表； 3、最复杂的一步，从前往后遍历列表，将相同值A的元素，根据所属数组取出，分别组成列表；接着，如果下个元素跟前面的值A不同，则将另一个数组的下个元素取出，进行比较，如果相等，则根据所属数组，分别加入前面列表；直到出现不同元素，如果哪个小，则将此列表中元素，与另一个列表的元素，根据下标进行交换；结果是获得满足条件的最终列表； 4、遍历此最终列表，如果此数组中包含当前元素C下标在内的后面所有元素个数之和+另一个数组中包含当前元素D下标在内的后面所有元素个数之和>=剩余要取的k位数组个数，则将此数字加入目标数组的下一位；同时将此元素从列表中剔出，以优化效率；如果不满足，而继续遍历下一个。最终获得目标数据。

由于第3步过于复杂，尚未拿出代码过程；但第4步已经完成，给大家作为参考；而且如果没有相同元素，则无需第3步，即可完成此算法。

public static int[] maxNumber(int[] nums1, int[] nums2, int k) { List<ListBean> list = new ArrayList<>(); addArray2List(nums1, list); addArray2List(nums2, list); Collections.sort(list, new Comparator<ListBean>() { @Override public int compare(ListBean o1, ListBean o2) { // TODO Auto-generated method stub // 倒序 return o2.value – o1.value; } }); System.out.println(“排序后的结果：”); for (ListBean bean : list) { System.out.println(bean.getValue() + “:” + bean.getKey() + “:” + bean.getIndex()); } System.out.println(“————–“); int[] result = new int[k]; getProperBig(nums1, nums2, k, -1, -1, result, list, 0); System.out.println(“最终结果：”); for (int i = 0; i < result.length; i++) { System.out.println(result[i]); } return result; } private static int[] getProperBig(int[] nums1, int[] nums2, int leftNumber, int num1Index, int num2Index, int[] result, List<ListBean> list, int listIndex) { if (list.size() > 0 && list.size() > listIndex) { ListBean bean = list.get(listIndex); if (bean.getKey() == 1) { if (bean.index > num1Index) { int leftCount1 = nums1.length – bean.index; int leftCount2 = nums2.length – (num2Index == -1 ? 0 : num2Index); if ((leftCount1 + leftCount2) >= leftNumber) { result[result.length – leftNumber] = bean.value; list.remove(listIndex); listIndex = 0; leftNumber–; num1Index = bean.index; } else { // 进入下个循环 listIndex++; } } else { // 进入下个循环 listIndex++; } } else { if (bean.index > num2Index) { int leftCount1 = nums1.length – (num1Index == -1 ? 0 : (num1Index + 1)); int leftCount2 = nums2.length – bean.index; if ((leftCount1 + leftCount2) >= leftNumber) { result[result.length – leftNumber] = bean.value; list.remove(listIndex); listIndex = 0; leftNumber–; num2Index = bean.index; } else { // 进入下个循环 listIndex++; } } else { // 进入下个循环 listIndex++; } } } if (leftNumber == 0) { return result; } return getProperBig(nums1, nums2, leftNumber, num1Index, num2Index, result, list, listIndex); } private static void addArray2List(int[] nums, List<ListBean> list) { ListBean bean; int key = list.size() > 0 ? 2 : 1; for (int i = 0; i < nums.length; i++) { bean = new ListBean(key, i, nums[i]); list.add(bean); } } public static void main(String[] args) { int[] nums1 = new int[] { 3, 4, 6, 5 }; int[] nums2 = new int[] { 9, 1, 2, 5, 8, 3 }; maxNumber(nums1, nums2, 5); } public static class ListBean { private int key = 0; private int index = 0; private int value = 0; public ListBean(int key, int index, int value) { super(); this.key = key; this.index = index; this.value = value; } public int getKey() { return key; } public void setKey(int key) { this.key = key; } public int getIndex() { return index; } public void setIndex(int index) { this.index = index; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } }