LeetCode 26：删除有序数组中的重复项

通知：吴师兄学算法训练营第十期开启报名，预计 12 月 20 开营，解锁 400 题。

一、题目描述

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

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。

你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

二、题目解析

设置两个索引 i 和 j 分别指向 nums1 和 nums2 的有效元素的尾部，从它们的尾部开始向前遍历。

同时设置索引 cur 指向 nums1 的最末尾。

在每次遍历过程中，比较 i 和 j 指向的元素值大小，把大的元素填充到 cur 的位置，填充完毕说明那个元素已经放置在它应该放置的位置，不需要在管它了，把 cur 向前移动，同时把 i 或者 j 向前移动。

继续比较 i 和 j 指向的元素值大小，把大的元素填充到 cur 的位置。

三、参考代码

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 索引从有序数组 nums1 有效元素的末端开始
        // 数组的下标索引从零开始计数
        // 索引   0    1     2
        // 数组 [ 1 ,  2  ,  3 ]
        int i = m - 1;

// 索引从有序数组 nums2 的末端开始
        int j = n - 1;

// 从有序数组 nums1 最末端的位置开始保存元素
        int cur = nums1.length - 1;

// 通过循环把 num2 的元素都移动到 num1 中
        while( j >= 0  ){

// 比较 num1 和 num2 中当前的元素大小

// 如果 num1 中的索引位置为 i 的元素大于 num2 中索引位置为 j 的元素
            // 为了防止越界 i 必须是大于等于 0 
            if( i >=0 && nums1[i] > nums2[j] ){

// 把 num1 中的索引位置为 i 的元素复制到索引为 cur 的位置
             // 此时 cur 的元素已经确定下来
             nums1[cur] = nums1[i];

// 接下来去确定 cur 前面一个元素应该放什么数字
             cur--;
             // 此时，索引 i 需要向前移动
             i--;
             // 否则，如果 num1 中的索引位置为 i 的元素小于或者等于 num2 中索引位置为 j 的元素
            }else{

// 把 num2 中的索引位置为 j 的元素复制到索引为 cur 的位置
             nums1[cur] = nums2[j];
             // 接下来去确定 cur 前面一个元素应该放什么数字
             cur--;
             // 此时，索引 j 需要向前移动
             j--;
            }
        }
    }
}