题目

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

coding

class Solution {
    /**
        为了保证第一个数组中的值不被覆盖，这是使用逆序的双指针来完成（这里其实类似归并排序）
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int idx = m + n -1;
        int i = m - 1;
        int j = n - 1;

        while(i >= 0 && j >= 0){
            if(nums1[i] >= nums2[j]){
                nums1[idx] = nums1[i];
                idx --;
                i --;
            }else{
                 nums1[idx] = nums2[j];
                idx --;
                j --;
            }
        }
        // 因为i排完之后，j很有可能还有值
        while(j >= 0){
            nums1[idx] = nums2[j];
            idx --;
            j --;
        }
    }
}

总结

这题可以使用归并排序的思想，使用双指针分别比较两个数组中的结果（这里使用的是倒序双指针得方式，因为我们的结果需要保存在第一个数组中，为了保证我们的死一个数组不出现数据被覆盖的问题所以使用了倒序双指针）
难点在于，因为我们的条件是i >= 0 && j >= 0，所以很有可能当i遍历结束的时候，但是j还是需要继续遍历
所以我们在i排完之后，需要将j对应的第二个数组重新继续遍历到结束

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96102.html

leetcode 88. 合并两个有序数组

题目

coding

总结

相关推荐

分享到: