408、有效单词缩写

88、合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

链接：https://leetcode-cn.com/problems/merge-sorted-array

题解

1、合并后排序

先将nums2的数据拷贝到nums1的空余部分，再进行排序

// 自己实现排序算法
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 插入排序
        if (nums2 == null || nums2.length == 0) {
            return;
        }
        // 组合成部分有序的数组
        for (int i = m,j = 0;i < m+n;i++) {
            nums1[i] = nums2[j++];
        }
        if (m == 0) {
            return;
        }
        // 插入排序完成排序过程
        int len = m+n;
        for (int i = m;i < len;i++) {// 待排序的部分
            if (nums1[i-1] <= nums1[i]) {
                break;
            }
            for (int j = 0;j < i;j++) {
                // 找到第一个大于目标值的下标j
                if (nums1[j] > nums1[i]) {
                    int t = nums1[i];
                    // 数据后移
                    for (int k = i;k > j; k--) {
                        nums1[k] = nums1[k-1];
                    }
                    // 数据
                    nums1[j] = t;
                    break;
                }
            }
        }
    }
}

// 调用Java API函数
class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    System.arraycopy(nums2, 0, nums1, m, n);
    Arrays.sort(nums1);
  }
}

// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetcode/

双指针 从前往后遍历

从前往后插入数据。

两个指针从两个数组开始处遍历，需要用空间换时间，利用复制数组来处理。

class Solution {
    public void merge(int[] nums1,int m,int nums2,int n) {
        int[] nums1_copy = new int[m];
        System.arraycopy(nums1,0,nums1_copy,0,m);

        // 处理nums1_copy和nums2的指针
        int p1 = 0, p2 = 0;

        // 处理nums1的指针
        int p;

        while (p1 < m && p2 < n) {
            nums1[p++] = nums1_copy[p1] < nums2[p2] ? nums1_copy[p1++] : nums2[p2++];
        }
        // 后续处理
        while (p1 < m) {
            nums1[p++] = nums1_copy[p1++];
        }

        while(p2 < n) {
            nums1[p++] = nums2[p2++];
        }
        // 调用API进行后续处理
        // if (p1 < m)
        //     System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
        // if (p2 < n)
        //     System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);

    }
}

3、双指针 从后往前遍历

从后往前插入数据

由于nums1数组有足够的空间，可以直接从后往前插入数据，而不需要额外的空间。

class Solution {
    public void merge(int[] nums1,int m,int[] nums2,int n) {
        int p1 = m-1;// nums1的遍历指针
        int p2 = n-1;// num2的遍历指针
        int p = m+n-1;// 合并后的数组的遍历指针
        while(p1 >= 0 && p2 >= 0) {
            // 大的数字排在后面
            nums1[p--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
        }
        // nums2还没有copy完
        while (p2 >= 0) {
            nums1[p--] = nums[p2--];
        }
        // System.arraycopy(nums2,0,nums1,0,p2+1);
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com