This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 88 on LeetCode. Merge two ordered arrays.

Tag: “double pointer”, “sort”

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 =,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

Tip:

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • –
    1 0 9 10^9     <= nums1[i], nums2[i] <=
    1 0 9 10^9

Double pointer (extra space)

A simple way to do this is to create an array arrarrarr as long as nums1NUMs1nums1, and use a double pointer to migrate num1num1num1 and nums2NUMs2nums2 to arrarrarr.

Finally, copy the arrarrarr to nums1NUMs1nums1.

Code:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int total = m + n;
        int[] arr = new int[total];
        int idx = 0;
        for (int i = 0, j = 0; i < m || j < n;) {
            if (i < m && j < n) {
                arr[idx++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
            } else if (i < m) {
                arr[idx++] = nums1[i++];
            } else if (j < n) {
                arr[idx++] = nums2[j++];
            }
        }
        System.arraycopy(arr, 0, nums1, 0, total); }}Copy the code
  • Time complexity: O(m+n)O(m +n)O(m +n)
  • Space complexity: O(m+n)O(m +n)O(m +n)

Merge first, sort later

We can also first migrated to the contents of nums2nums2nums2 nums1nums1nums1 go, again to nums1nums1nums1 sort.

Code:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2, 0, nums1, m, n); Arrays.sort(nums1); }}Copy the code
  • Time complexity: O ((m + n) log (m + n) O (log (m + n) {} (m + n)) O ((m + n) log (m + n))
  • Space complexity: O(1)O(1)O(1)

Sort in Ps.java is a comprehensive sort. Contains insert/biaxial quicksort/merge /timsort, assumed hereArrays.sortIt uses “biaxial quicksort” and ignores the space cost of recursion.

Merge in place (front to back)

You can also merge directly at nums1nums1nums1, but you need to make sure that the nums2nums2nums2 pointer points to the smallest element at the start of each loop.

Therefore, we need to perform a local sort on nums2nums2nums2.

Code:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = 0, j = 0;
        while (j < n) {
            if (i >= m) {
                nums1[i] = nums2[j++];
            } else {
                int a = nums1[i], b = nums2[j];
                if (a > b) swap(nums1, i, nums2, j);
                sort(nums2, j, n - 1); } i++; }}void sort(int[] nums, int l, int r) {
        if (l >= r) return;
        int x = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);
            if (i < j) swap(nums, i, nums, j);
        }
        sort(nums, l, j);
        sort(nums, j + 1, r);
    }
    void swap(int[] nums1, int i, int[] nums2, int j) {
        inttmp = nums1[i]; nums1[i] = nums2[j]; nums2[j] = tmp; }}Copy the code
  • O(n+m2logm)O(n +m ^2 log{m})O(n+m2logm)
  • Space complexity: ignore recursive overhead, complexity is O(1)O(1)O(1)

Merge in place (from back to front)

The idea is similar to “Method 1”. If the traversal direction is changed from “front to back” to “back to front”, the space complexity of O(1)O(1)O(1) can be achieved.

Code:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1;
        int idx = m + n - 1;
        while (i >= 0 || j >= 0) {
            if (i >= 0 && j >= 0) {
                nums1[idx--] = nums1[i] >= nums2[j] ? nums1[i--] : nums2[j--];
            } else if (i >= 0) {
                nums1[idx--] = nums1[i--];
            } else{ nums1[idx--] = nums2[j--]; }}}}Copy the code
  • Time complexity: O(m+n)O(m +n)O(m +n)
  • Space complexity: O(1)O(1)O(1)

The last

This is the 88th article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks. We will finish all the topics without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.