This is the third day of my participation in the August Text Challenge.More challenges in August

Topic describes

You are given two non-descending arrays of integers, nums1 and nums2, and two integers, m and n, representing the number of elements in nums1 and nums2, respectively. Please merge nums2 into nums1 so that the merged array is also in non-descending order. Note: Finally, the merged array should not be returned by the function, but stored in the array nums1. To deal with this, nums1 has an initial length of m + n, where the first m elements represent the elements that should be combined and the last n elements are0, should be ignored. Nums2 has a length of n. The sample1: Input: nums1 = [1.2.3.0.0.0], m = 3, nums2 = [2.5.6], n = 3Output:1.2.2.3.5.6] Explanation: need to merge [1.2.3] and [2.5.6]. The combined result is [1.2.2.3.5.6], where the elements in italic bold are nums1. The sample2: Input: nums1 = [1], m = 1, nums2 = [], n = 0Output:1] Explanation: need to merge [1] and []. The combined result is [1]. The sample3: Input: nums1 = [0], m = 0, nums2 = [1], n = 1Output:1The arrays to merge are [] and [].1]. The combined result is [1]. Notice, because m is equal to0So there are no elements in nums1. Only existing in NUMs10Just to make sure that the merge results can be safely stored in NUMs1. Nums1. length == m + n nums2.length == n0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109Advanced: Can you design and implement a time complexity O(m + N) algorithm to solve this problem? Source: LeetCode//leetcode-cn.com/problems/merge-sorted-arrayCopyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Ideas & CODE

1. Sort arrays by merging them

The easiest way to solve this problem is to simply merge the values of the two arrays and sort the combined arrays

public void merg(int[] nums1, int m, int[] nums2, int n) {
    int index = 0;
    for (int i = m; i < m + n; i++) {
        nums1[i] = nums2[index++];
    }
    Arrays.sort(nums1);
}
Copy the code

Because arrays.sort () uses fast sorting, the time complexity of this algorithm is O(logn)

2. Double pointer solution

Write the first kind of thinking after a long time also have no other optimization ideas, see the official problem solution, found that can do with double Pointers, long way to repair xi, also many brush point thinking will become more flexible!

So they’re giving us two arrays, and they’re both sorted, and they’re monotonically increasing, so we can simplify the algorithm by taking advantage of that.

  • First think of two arrays as two queues, define, define two Pointers (indexes) to the queue head.
  • Each time the loop compares the size of two opposing elements, the smaller one is inserted into the new sorted array, and the pointer is moved one bit further back.
  • In this case, one queue must be empty and the other queue has an element, so just add that element to the end of the sorted array
public static void merge(int[] nums1, int m, int[] nums2, int n) {
    int a = 0;
    int b = 0;
    int c = 0;
    int[] sortArr = new int[m + n];
    while (a < m || b < n) {
        if (a == m) {
            sortArr[c++] = nums2[b++];
        } else if (b == n) {
            sortArr[c++] = nums1[a++];
        } else if (nums1[a] <= nums2[b]) {
            sortArr[c++] = nums1[a++];
        } else{ sortArr[c++] = nums2[b++]; }}for (int i = 0; i < sortArr.length; i++) { nums1[i] = sortArr[i]; }}Copy the code

This algorithm only needs to iterate through the array once, and the time complexity is O(m+n) = O(1).