3623. Merge two ordered arrays

Here are two buttons Non decreasing order Array of arranged integers nums1 and nums2, There are two other integers m and n , respectively nums1 and nums2 The number of elements in . Would you please Merge nums2 To nums1 in , Make the merged array press Non decreasing order array . Be careful ： Final , The merged array should not be returned by the function , It's stored in an array nums1 in . In response to this situation ,nums1 The initial length of is m + n, The top m Elements represent the elements that should be merged , after n Elements are  0 , It should be ignored .nums2 The length of is n .    Example  1： Input ：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output ：[1,2,2,3,5,6] explain ： Need merger [1,2,3] and [2,5,6] . The combined result is [1,2,2,3,5,6] , In which, bold italics indicates nums1 The elements in . Example  2： Input ：nums1 = [1], m = 1, nums2 = [], n = 0 Output ：[1] explain ： Need merger [1] and [] . The combined result is [1] . Example  3： Input ：nums1 = [0], m = 0, nums2 = [1], n = 1 Output ：[1] explain ： The array to be merged is [] and [1] . The combined result is [1] . Be careful , because m = 0 , therefore nums1 No elements in .nums1 The only remaining  0  Just to ensure that the merged results can be successfully stored in nums1 in .    Tips ： nums1.length == m + n nums2.length == n 0 <= m, n <= 200 1 <= m + n <= 200 -109 <= nums1[i], nums2[j] <= 109    Advanced ： You can design and implement a time complexity of O(m + n) Does the algorithm solve this problem ？ source ： Power button （LeetCode） link ：https://leetcode-cn.com/problems/merge-sorted-array Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

package cn.fansunion.leecode.linkedlist; /**  * 88. Merge two ordered arrays <br/> Here are two buttons Non decreasing order Array of arranged integers nums1 and nums2, There are two other integers m and n , respectively nums1 and nums2 The number of elements in .  *  * Would you please Merge nums2 To nums1 in , Make the merged array press Non decreasing order array .  *  * Be careful ： Final , The merged array should not be returned by the function , It's stored in an array nums1 in . In response to this situation ,nums1 The initial length of is m + n, The top m Elements represent the elements that should be merged , after n Elements are 0 , It should be ignored .nums2 The length of is n .  *  * source ： Power button （LeetCode） link ： Power button   Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .  *  * @author [email protected]  *  *         2022-2-23  */ public class MergeSortedArray {     /* Example 1：            Input ：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3      Output ：[1,2,2,3,5,6]      explain ： Need merger [1,2,3] and [2,5,6] .      The combined result is [1,2,2,3,5,6] , In which, bold italics indicates nums1 The elements in .      Example 2：            Input ：nums1 = [1], m = 1, nums2 = [], n = 0      Output ：[1]      explain ： Need merger [1] and [] .      The combined result is [1] .      Example 3：            Input ：nums1 = [0], m = 0, nums2 = [1], n = 1      Output ：[1]      explain ： The array to be merged is [] and [1] .      The combined result is [1] .      Be careful , because m = 0 , therefore nums1 No elements in .nums1 The only remaining 0 Just to ensure that the merged results can be successfully stored in nums1 in .            Tips ：           nums1.length == m + n     nums2.length == n     0 <= m, n <= 200     1 <= m + n <= 200     -109 <= nums1[i], nums2[j] <= 109*/     /**      * Ideas ： The goal is to nums2 Insert into in order nums1, Compare insert from back to front ; Double pointer , Efficient ;<br/>      * If nums2 There are some left not inserted , It needs to be inserted separately <br/>      * If nums1 There are some left not inserted , No need to deal with , Characteristic is processing nums2,nums2 What is not handled is naturally orderly <br/>      * The official scientific name of the algorithm ：“ Reverse double pointer ”. Because algorithm problems are often all kinds of “ ideas ”,“ Trick ”, Suddenly thought of ： It's easier from back to front , Gradually replace “0” The process of      * This question is “ Merge array ”, There are specific requirements ; Common merge arrays ：nums1+nums2, Can directly new One nums3, Positive traversal nums1 and nums2      *      *      * @param nums1      * @param m      * @param nums2      * @param n      */     public void merge(int[] nums1, int m, int[] nums2, int n) {         int nums1Index = m - 1;         int nums2Index = n - 1;         int curIndex = m + n - 1;         while (nums1Index >= 0 && nums2Index >= 0) {             if (nums1[nums1Index]<= nums2[nums2Index]) {                 nums1[curIndex] = nums2[nums2Index];                 nums2Index--;                 curIndex--;             } else {                 nums1[curIndex] = nums1[nums1Index];                 nums1Index--;                 curIndex--;             }         }         // nums1 Moved back in advance ,nums2 And the rest         // This topic , Boundary value cases often occur , I can't think all at once , Many test cases have to be constructed         while (nums2Index >= 0) {             nums1[nums2Index] = nums2[nums2Index];             nums2Index--;         }     }     /**      * Merge two ordered arrays （ Stupid way ）, The result is not right <br/>      * [-1,0,0,3,3,3,0,0,0] 6,[1,2,2] 3; Output ：[1,2,2,-1,0,0,3,3,3], expect ：[-1,0,0,1,2,2,3,3,3]      *      * @param nums1      *            nums1 = [1,2,3,0,0,0]      * @param m      *            3 nums2 = [2,5,6]      * @param nums2      *            3      * @param n      *            3 Output ：[1,2,2,3,5,6] explain ： Need merger [1,2,3] and [2,5,6] .      */     public void mergeStupidAndError(int[] nums1, int m, int[] nums2, int n) {         // Traverse a number of numbers that need to be inserted         for (int nums2Index = 0; nums2Index < n; nums2Index++) {             // Insert 1 A number into the target array             mergeIntoNums(nums2[nums2Index], nums1);         }     }     // Insert 1 A number into the target array     private void mergeIntoNums(int newNum, int[] nums) {         // Find the insertion position first         int insertIndex = 0;         for (int i = 0; i < nums.length; i++) {             if (nums[i] <= 0 || newNum < nums[i]) {                 insertIndex = i;                 break;             }             insertIndex++;         }         // adopt 2 Auxiliary of temporary variables , Insert , effect ： The following numbers are all moved back one digit         int cur = newNum;         int next = 0;         for (int index = insertIndex; index < nums.length; index++) {             next = nums[index];             nums[index] = cur;             cur = next;         }     }     /**      * Another form of merged array , Allows the construction of new merge Array and return , A little bit simpler      *      * @param nums1      * @param nums2      * @return      */     public int[] mergeWithReturn(int[] nums1, int[] nums2) {         int[] nums = new int[nums1.length + nums2.length];         int nums1Index = 0;         int nums2Index = 0;         int curIndex = 0;         // Double pointer         while (nums1Index < nums1.length && nums2Index < nums2.length) {             if (nums1[nums1Index] <= nums2[nums2Index]) {                 nums[curIndex] = nums1[nums1Index];                 nums1Index++;             } else {                 nums[curIndex] = nums2[nums2Index];                 nums2Index++;             }             curIndex++;         }         // num1 There's a surplus         while (nums1Index < nums1.length) {             nums[curIndex] = nums1[nums1Index];             nums1Index++;             curIndex++;         }         // nums2 There's a surplus         while (nums2Index < nums2.length) {             nums[curIndex] = nums2[nums2Index];             nums2Index++;             curIndex++;         }         return nums;     } }

package test.leecode.linkedlist; import org.junit.Assert; import org.junit.Test; import cn.fansunion.leecode.linkedlist.MergeSortedArray; /**  * @author [email protected]  *  *         2022-2-23  */ public class MergeSortedArrayTest {     @Test     public void test() {         MergeSortedArray test = new MergeSortedArray();         // test2         int[] nums3 = new int[] { 2, 3, 5, 0, 0, 0, 0, 0};         int[] nums4 = new int[] { 1, 4, 5, 6, 9};         test.merge(nums3, 3, nums4, 5);         Assert.assertArrayEquals(new int[] { 1, 2, 3, 4, 5, 5, 6, 9}, nums3);         // test1         int[] nums1 = new int[] { 1, 2, 3, 0, 0, 0};         int[] nums2 = new int[] { 2, 5, 6};         test.merge(nums1, 3, nums2, 3);         Assert.assertArrayEquals(new int[] { 1, 2, 2, 3, 5, 6}, nums1);         // test3         int[] nums5 = new int[] { 3, 3, 3, 3, 0, 0, 0, 0};         int[] nums6 = new int[] { 1, 1, 2, 2};         test.merge(nums5, 4, nums6, 4);         Assert.assertArrayEquals(new int[] { 1, 1, 2, 2, 3, 3, 3, 3}, nums5);         // test4         int[] nums7 = new int[] { 1, 1, 2, 3, 0, 0, 0, 0};         int[] nums8 = new int[] { 4, 5, 6, 7};         test.merge(nums7, 4, nums8, 4);         Assert.assertArrayEquals(new int[] { 1, 1, 2, 3, 4, 5, 6, 7}, nums7);     }     @Test     public void testMergeWithReturn() {         MergeSortedArray test = new MergeSortedArray();         // test2         int[] nums3 = new int[] { 2, 3, 5};         int[] nums4 = new int[] { 1, 4, 5, 6, 9};         int[] test2 = test.mergeWithReturn(nums3, nums4);         Assert.assertArrayEquals(new int[] { 1, 2, 3, 4, 5, 5, 6, 9}, test2);         // test1         int[] nums1 = new int[] { 1, 2, 3};         int[] nums2 = new int[] { 2, 5, 6};         int[] test1 = test.mergeWithReturn(nums1, nums2);         Assert.assertArrayEquals(new int[] { 1, 2, 2, 3, 5, 6}, test1);         // test3         int[] nums5 = new int[] { 3, 3, 3, 3};         int[] nums6 = new int[] { 1, 1, 2, 2};         int[] test3 = test.mergeWithReturn(nums5, nums6);         Assert.assertArrayEquals(new int[] { 1, 1, 2, 2, 3, 3, 3, 3}, test3);         // test4         int[] nums7 = new int[] { 1, 1, 2, 3};         int[] nums8 = new int[] { 4, 5, 6, 7};         int[] test4 = test.mergeWithReturn(nums7, nums8);         Assert.assertArrayEquals(new int[] { 1, 1, 2, 3, 4, 5, 6, 7}, test4);     }     // mergeStupid     public static void main(String[] args) {         // test1         int[] nums1 = new int[] { 1, 2, 3, 0, 0, 0};         int[] nums2 = new int[] { 2, 5, 6};         MergeSortedArray msa = new MergeSortedArray();         msa.mergeStupidAndError(nums1, 3, nums2, 3);         for (int num : nums1) {             System.out.print(num);         }         System.out.println();         // test2         int[] nums3 = new int[] { 2, 3, 5, 0, 0, 0, 0, 0};         int[] nums4 = new int[] { 1, 4, 5, 6, 9};         MergeSortedArray msa2 = new MergeSortedArray();         msa2.mergeStupidAndError(nums3, 3, nums4, 5);         for (int num : nums3) {             System.out.print(num);         }     } }