This is the 28th day of my participation in Gwen Challenge

Title description:

The original address

Merge nums2 into nums1 to make nums1 an ordered array.

Initialize nums1 and nums2 to m and n, respectively. You can assume that nums1 has a space size equal to m + n so that it has enough space to hold elements from Nums2.

The sample a

Input: nums1 =,2,3,0,0,0 [1], m = 3, nums2 = [6] 2, n = 3 output:,2,2,3,5,6 [1]Copy the code

Example 2

Input: nums1 = [1], m = 1, nums2 = [], n = 0Copy the code

prompt

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200

  • 1 0 9 < = n u m s 1 [ i ] . n u m s 2 [ i ] < = 1 0 9 10^9 <= nums1[i], nums2[i] <= 10^9

Thought analysis

Direct merge sort

There’s nothing to say about this, just merge the two arrays and sort them. In Java, merges can be copied quickly using the System. arrayCopy method.

Two-pointer method (front to back)

So if we look at the problem again, these are two sorted arrays, so we just need to take the first number out of each array, compare it, sort it as they say, and obviously, we need two Pointers to the heads of each array.

AC code

Direct merger

    class Solution {
    fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
        java.lang.System.arraycopy(nums2, 0, nums1, m, n)
        java.util.Arrays.sort(nums1)
    }
}
Copy the code

Double pointer method

   class Solution {
    fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
        var nums1_copy = IntArray(m)
        java.lang.System.arraycopy(nums1, 0, nums1_copy, 0, m)
    
        var p1 = 0
        var p2 = 0
    
        var p = 0
        
        while ((p1 < m) && (p2 < n)) {
    
            nums1[p++] =  if (nums1_copy[p1] < nums2[p2]) {
                nums1_copy[p1++]
            } else {
                nums2[p2++]
            }
        }
        if (p1 < m) {
            java.lang.System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2)
        }
        if (p2 < n) {
            java.lang.System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2)
        }
        
    }
}
Copy the code

conclusion

This problem did not see the solution, probably think of the above two solutions, and then to turn over the solution, found that there is room for optimization of solution two, and indeed there is no best, only better. In fact, the brush is too little, not sensitive to the algorithm or the time complexity or space complexity, limited to solving the problem first, hopefully better and better.

reference

State the problem solving

88. Merge two ordered arrays