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;
        }

    }