関小君刷题记

题目大意：

拼接最大数

给定长度分别为 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]

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=321

解题思路：

这道题还是有点难度的，想了许久才搞懂思路。简单来看，题目是要求在两组数中分别找到k1个数字和k2个数字，k1 + k2 = k，且这些数字在原数组中的相对顺序保持不变，最终这些数字组合在一起能形成一个最大的数。大体思路如下：

1. 写出一个方法，能够求出在一个数组中抽取k个数，能组成的最大数字
2. 将长度k分成两部分，k1和k2，且 k1 + k2 = k。k1从0循环至k，分别使用k1和k2在两个数组中找出其最大的数字，再将两个数字合并成一个当前最大数，循环结束后找到最大的那个即是结果。

具体来看，首先考虑，如何在一个数组中找到长度为k的最大数字组合？举个例子：

int [] num1 = {1, 8, 2, 9, 7};
int k = 3;

// maxNumber = 897;

这个例子很明显，在数组num1中，找出3位数，最大的肯定是897。(注意题目要求最终组成的数字顺序要与在原数组中的相对位置保持一致，如果不要求顺序的话，最大值肯定是987。)那么，用程序逻辑来思考，897是如何得到的呢？例子中k为3，说明最高位是百位，百位上的数字肯定是越大越好，但是这个最大数是不能从数组所有范围内选材的，百位意味着后面还有两位数字（十位和个位），所以，百位的选材范围应该是数组的第一个元素到数组的倒数第三个元素为止。例子中百位数在num1中的选材范围因该是{1, 8, 2}，所以百位为8，按照顺序，十位数的选材范围应该在8之后，并且考虑到之后还有个位数，所以范围应该在倒数第二个元素之前。因此，这个例子的执行逻辑应该是：

int [] num1 = {1, 8, 2, 9, 7};
int k = 3;

max {1, 8, 2} = 8; // 百位
max {2, 9} = 9; // 十位
max {7} = 7; // 个位

这样，我们可以在一个数组中找到一个长度为k最大数，使用同样的方法可以在2个数组中分别找出长度为k1和k2的两个最大数，因为k1 + k2 = k，所以，再将这两个最大数组合到一起，就是最终的答案。不过，还有两个问题没有解决，第一，如何将长度k分为k1和k2？第二，如何将两个最大数合并成一个最大数？接下来我们分别说明。

将k分解成k1和k2，其实就是在数组1中选择k1个数字，在数组2中选择k2个数字，其中k1和k2都有可能为0，也就是说，最终结果的k个数字有可能是从一个数组中选择出来的。具体如何分k，我们无法得知，所以必须使用循环，遍历出每一种分配情况，从中选出最大的答案。循环中注意k1和k2不能大于对应数组的长度。即：

for (int i = 0; i <= k; i++) {
    int k1 = i;
    int k2 = k - i;
    if (k1 > nums1.length || k2 > nums2.length) {
        continue;
    }
    // do something
}

最后一个问题是如何合并两个最大数。我们可以从两个数字的最高位开始比较，将较大的一个数加入到结果数组的首位，并将此数的指针从其最高位向后移动一位，继续与另一数的当前位比较。直到全部比较结束。举个例子：

int[] maxNum1 = {5, 3, 9};
int[] maxNum2 = {7, 4};

// maxNum1[0] < maxNum2[0] (5 < 7)
int result[] = {7}
// maxNum1[0] > maxNum2[1] (5 > 4)
int result[] = {7, 5}
// maxNum1[1] < maxNum2[1] (3 < 4)
int result[] = {7, 5, 4}
// 此时maxNum2[2]已经越界，所以，将maxNum1 剩余数值按顺序添加到result即可
int result[] = {7, 5, 4, 3, 9}

这个思路不难理解，经典的merge sort算法也运用了这个逻辑。但是有一点是需要注意的，当比较时，当前位的两个数字相同时该如何处理？比如：

int[] maxNum1 = {1, 1, 9};
int[] maxNum2 = {1, 1, 8};

显然119118的组合要大于118119，简单来想，如果当前位两数相同，需要同时向后移动指针，直到不相同位出现，或者某一个数组越界，这时应将较大的一方或者还没有越界一方先加入到结果数组中。

最后看下完整代码：

int res[];

public int[] maxNumber(int[] nums1, int[] nums2, int k) {
    res = new int[k]; // 返回结果
    // 将k分成k1和k2两部分
    for (int i = 0; i <= k; i++) {
        int k1 = i;
        int k2 = k - i;
        // 如果k1大于数组1的长度或者k2大于数组2的长度，说明分组不合理，继续循环
        if (k1 > nums1.length || k2 > nums2.length) {
            continue;
        }
        // 在数组1中找到长度为k1的最大数，在数组2中找到长度为k2的最大数
        // 并将两个最大数进行合并
        merge(findMax(nums1, k1, 0, new int[k1], 0), findMax(nums2, k2, 0, new int[k2], 0));
    }
    return res;
}
/**
* 从一个数组中找出长度为size的最大数
* nums: 数组
* size: 最大数的位数
* startIndex: 当前位在数组中查找范围的起始位置
* max: 临时最大结果
*/private int[] findMax(int[] nums, int size, int startIndex, int[] max, int currentIndex) {
    // 位数为0还找个毛线
    if (size == 0) {
        return max;
    }
    // 这一步是优化代码时加上的。
    // 如果查找范围的起始位置到数组结束的长度与size相同，那么将起始位置之后的数都加入结果即可。
    // 比如从长度为3的数组中找出一个最大3位数
    if (nums.length - startIndex == size) {
        for (int i = startIndex; i < nums.length; i++) {
            max[currentIndex++] = nums[i];
        }
        return max;
    }
    // 当前位在数组中的查找范围的结束位置
    int endIndex = nums.length - size;
    // 找到的最大数对应在数组中的index。当前位下一位数应该在这个index之后开始查找
    int maxIndex = startIndex;
    for (int i = startIndex; i <= endIndex; i++) {
        if (nums[i] > max[currentIndex]) {
            max[currentIndex] = nums[i];
            maxIndex = i;
        }
    }
    // 递归寻找下一位
    return findMax(nums, size - 1, maxIndex + 1, max, currentIndex + 1);
}
// 合并两个最大数
private void merge(int[] nums1, int[] nums2) {
    // 在合并的同时，比较当前数，是否要大于原先的结果
    boolean isBiggerThanRes = false;
    // 创建临时结果，长度为两数组长度之和
    int[] merge = new int[nums1.length + nums2.length];
    int index1 = 0, index2 = 0, indexMerge = 0;
    while (index1 < nums1.length || index2 < nums2.length) {
        // 通过index1和index2比较当前位大小，将大数加入到结果，同时对应的index加一
        merge[indexMerge] = isNums1Bigger(nums1, nums2, index1, index2) ? nums1[index1++] : nums2[index2++];
        if (!isBiggerThanRes) {
            // 如果临时结果的当前位小于原先结果的同位，说明肯定不是最大数，结束当前操作
            if (merge[indexMerge] < res[indexMerge]) {
                return;
            } else if (merge[indexMerge] > res[indexMerge]) {
                isBiggerThanRes = true;
            }
        }
        indexMerge++;
    }
    res = merge;
}
// 判断第一个数组对应的当前位是否大于第二个数组的当前位
private boolean isNums1Bigger(int[] nums1, int[] nums2, int index1, int index2) {
    // 保证在两个数组都没有越界的前提下循环
    while (index1 < nums1.length && index2 < nums2.length) {
        // 第一个数组对应的当前位大返回true，否则返回false
        if (nums1[index1] > nums2[index2]) {
            return true;
        } else if (nums1[index1] < nums2[index2]) {
            return false;
        }
        // 如果相同继续比较下一位
        index1++;
        index2++;
    }
    // 循环结束后可能出现一个数组还没遍历完的情况，
    // 如果数组1还有剩余，说明数组1大于数组2，返回true
    return index1 < nums1.length;
}

本题解法用时7ms

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-321-create-maximum-number解题思路分析/