• Nuggets team number online, help you Offer impromptu! Click here for more details

Subject core

A simple algorithm every day to prevent Alzheimer’s disease

Topic describes

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.

Example 1: Input nums1 = [1,2,3,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Nums1 = [1], m = 1, nums2 = [], n = 0  nums1.length == m + n nums2.length == n 0 <= m, n <= 200 1 <= m + n <= 200 -109 <= nums1[i], nums2[i] <= 109Copy the code

Their thinking

The easiest way to do this is to iterate through the nums1 array and insert the values of the NUMs2 array.

Double pointer: nums1 and NUMs2 are two sorted arrays, so you can use this double pointer to achieve O(m+n) time complexity, O(m+n) space complexity algorithm.

Reverse double pointer: given that the length of n in the last half of NUMs1 is empty, we can use reverse double pointer for comparison interpolation. Achieve O(1) space complexity.

The problem solving code

Simple solution of violence

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

Double pointer

 public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {// if p1==m Then insert nums2
                cur = nums2[p2];
                p2++;
            } else if(p2 ==n) {if p2==n, the right side is finished. Nums1 cur = nums1[p1]; p1++; }else if (nums1[p1] < nums2[p2]) {
                Nums1 [0]; nums2[0]
                // If the left is less than the right, then p1 increases
                cur = nums1[p1];// Insert p1 into the sorted array
                p1++;
            } else {// Insert p2 into the sorted array
                cur = nums2[p2];
                p2++;
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }
Copy the code

Reverse double pointer

 public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1, p2 = n - 1;// The left pointer is the last digit in nums1, and the right pointer is the last digit in nums2
        int tail = m + n - 1;// Start in reverse order with subscript m+n-1
        int cur;
        while (p1 >= 0 || p2 >= 0) {//p1, p2 is less than 0
            if (p1 == -1) {
                cur = nums2[p2];
                p2--;
            } else if (p2 == -1) {
                cur = nums1[p1];
                p1--;
            } else if (nums1[p1] > nums2[p2]) {// Compare the size of the rightmost nums1 and nums2
                cur = nums1[p1];//nums1 is larger than nums2
                p1--;//p1 moves to the left
            } else {
                cur = nums2[p2];// Instead, P2 moves to the left
                p2--;
            }
            nums1[tail] = cur;// assign value=0 to the right of nums1tail--; }}Copy the code

# # to summarize

Simple algorithm, for preventing senile dementia, very good 👌