合并两个有序数组-88

主要考察归并排序得思想,本题方法很多

我自己写的非最优版本

   public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) {
            return;
        }

        if (m == 0) {
            for (int i = 0; i < n; i++) {
                nums1[i] = nums2[i];
            }
            return;
        }

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

        /**
         * [1,2,3,0,0,0]
         * 3
         * [4,5,6]
         * 3
         */

        /**
         * [1,0,0,0,0,0]
         * 1
         * [2,3,4,5,6]
         * 5
         */
        int first = 0;
        int second = 0;
        for (; first < m; ) {
            if (nums1[first] > nums2[second]) {
                swap(nums1, first, nums2, second);
                sortArrays(nums2);
            }
            first++;
        }

        for (second = 0; second < n; second++, first++) {
            nums1[first] = nums2[second];
        }
    }

    /**
     * * [2,3,4]
     */
    private void sortArrays(int[] nums2) {
        if (nums2.length < 2) {
           return;
        }

        for (int i = 0; i < nums2.length; i++) {
            if (i == nums2.length - 1) {
                return;
            }
            
            if (nums2[i] <= nums2[i + 1]) {
                break;
            }

            int temp = nums2[i];
            nums2[i] = nums2[i + 1];
            nums2[i + 1] = temp;
        }
    }

    public void swap(int[] nums1, int i, int[] nums2, int j) {
        int temp = nums1[i];
        nums1[i] = nums2[j];
        nums2[j] = temp;
    }

力扣合并两个有序数组-88https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0/

方法一:直接合并后排序

方法二:双指针

方法三:逆向双指针

上一篇:acwing算法基础课文字版(看不懂你打我)——第二课基础算法之:高精度算法(大数乘小数、大数除小数)


下一篇:肖SIR__数据库之运用__11.3