Leetcode 88. Merge two ordered arrays

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

1. Title 📑

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 are 0 and should be ignored. Nums2 has a length of n.

Example 1:

Input: nums1 =,2,3,0,0,0 [1], m = 3, nums2 = [6] 2, n = 3

Output:,2,2,3,5,6 [1]

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 italics and bold are nums1.

Example 2:

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

Output: [1]

Explanation: Need to merge [1] and [].

The combined result is [1].

Example 3:

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

Output: [1]

Explanation: The arrays to merge are [] and [1].

The combined result is [1].

Note that there are no elements in nums1 because m = 0. The only zeros left in NUMs1 are simply to ensure that the merge results can be safely stored in NUMs1.

Limitations:

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109

2. Ideas 🧠

Method 1: sort after merge directly

  1. willnums2Array copy tonums1The back of the
  2. rightnums1And when you sort that, you get the array in question

Method two: double pointer

To perfect!

3. Code: 👨💻

Commit AC for the first time

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if(m == 0) nums1[0] = nums2[0];
        for(inti = m; i < nums1.length && n ! =0; i++) {
            nums1[i] = nums2[--n];
        }
        BubbleSort(nums1);
    }

    public static void BubbleSort(int arr[]) {
        for(int e = arr.length - 1; e > 0; e--) {
            for(int i = 0; i < e; i++) {
                if(arr[i] > arr[i + 1])
                    swap(arr, i, i + 1); }}}public static void swap(int arr[], int i, int j) {
        inttemp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}Copy the code

Time complexity: O((m + N) * log(m +n)) The length of the sorting sequence is M + N, using the time complexity of quicksort, the average case is O((M + N) log(m +n)).

Space complexity: O(log(m + n))

Commit the SECOND TIME

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
         int i = nums1.length ;

        while (n > 0) {
            if (m > 0 && nums1[m-1] > nums2[n-1]) {
                nums1[--i] = nums1[--m]; 
                / / instead of swap
            }else{
                nums1[--i] = nums2[--n]; 
                / / instead of swap}}}}Copy the code

Time complexity: O(m +n) sorting sequence length is M + N

Space complexity: O(m + N)

4, summarize

The problem of sorting is examined, but also examined the flexible use of double Pointers, if the analysis of the problem from the beginning cannot achieve the expected results, you can try to start from the end of the search.

❤️ from the LeetCode Basic Algorithms column subscribe to ❤️

The original intention of the director to write blog is very simple, I hope everyone in the process of learning less detours, learn more things, to their own help to leave your praise 👍 or pay attention to ➕ are the biggest support for me, your attention and praise to the director every day more power.

If you don’t understand one part of the article, you can reply to me in the comment section. Let’s discuss, learn and progress together!

88. Merge two ordered arrays – LeetCode