LeetCode 每日一题 [5] 合并排序的数组

LeetCode 面试题 10.01. 合并排序的数组 [简单]

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sorted-merge-lcci

示例:

输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

说明:

• A.length == n + m

题目分析

方法1：

直接追加到末尾，然后排序 不过给的方法没有用到n，我就发现了不寻常之处

方法2：

需要比较 m + n 个数的大小，所以先保证其中至少 m 或 n 个数比较完毕并放在正确位置，再考虑剩下的数。
注意 m 和 n 是未遍历的、有效的数字的个数，不是下标，作为下标要 -1−1 。

核心思想是为了防止前面的数据被覆盖。而且数据是从后面向前面添加，也就是比较
A数组的有效值部分和B数组的最后一个，取大的哪个数据放在最后面，
如果B有剩下的数据，那么就说明，A已经派完了，而B剩余的数据有序，就直接放到A对应位置即可

方法3：

3.1 先把A的有效数据移动到最后面
3.2 然后把A和B的有效数据进行比较，小的放在前面。然后指向索引的值变化，直到有结束，然后如果m或者n还是有值，就直接CV一下，结束

代码实现

public class LeetCode_05_SortedMergeLCCI {
    public static void main(String[] args) {
        int[] A = {1, 2, 3, 0, 0, 0};
        int[] B = {2, 5, 6};
        int m = 3, n = 3;
        merge03(A, m, B, n);
        for (int num : A) {
            System.out.print(num + " ");
        }
    }

    /**
     * 思想是把A的数据拿到后面去，然后比较填充前面的数据
     */
    public static void merge03(int[] A, int m, int[] B, int n) {
        System.arraycopy(A, 0, A, n, m);
        int index = 0;
        int indexA, indexB;
        for (indexA = n, indexB = 0; indexA < m + n && indexB < n; ) {
            if (A[indexA] <= B[indexB]) {
                A[index++] = A[indexA++];
            } else {
                A[index++] = B[indexB++];
            }
        }
        while (indexB < n) {
            A[index++] = B[indexB++];
        }
    }

    /**
     * 需要比较 m + n 个数的大小，所以先保证其中至少 m 或 n 个数比较完毕并放在正确位置，再考虑剩下的数。
     * 注意 m 和 n 是未遍历的、有效的数字的个数，不是下标，作为下标要 -1−1 。
     * <p>
     * 核心思想是为了防止前面的数据被覆盖。而且数据是从后面向前面添加，也就是比较
     * A数组的有效值部分和B数组的最后一个，取大的哪个数据放在最后面，
     * 如果B有剩下的数据，那么就说明，A已经派完了，而B剩余的数据有序，就直接放到A对应位置即可
     */
    public static void merge02(int[] A, int m, int[] B, int n) {
        while (m > 0 && n > 0) {
            A[m + n - 1] = A[m - 1] > B[n - 1] ? A[--m] : B[--n];
        }
        while (n > 0) {
            A[n - 1] = B[n - 1];
            n--;
        }
    }

    /**
     * 直接追加到末尾，然后排序 不过给的方法没有用到n，我就发现了不寻常之处
     */
    public static void merge(int[] A, int m, int[] B, int n) {
        int targetIndex = 0;
        for (int i = m; i < A.length; i++) {
            A[i] = B[targetIndex];
            targetIndex++;
        }
        Arrays.sort(A);
    }
}