Leetcode daily practice - 88. Merge two ordered arrays

Preface

Wassup guys！ I am a Edison

It's today LeetCode Upper leetcode 88. Merge two ordered arrays

Let’s get it！

---

---

1. Topic analysis

Here are two buttons Non decreasing order Array of arranged integers nums1 and nums2, There are two other integers m and n , respectively nums1 and nums2 The number of elements in .

Example 1：

Example 2：

Example 3：

2. Title diagram

The decreasing Explanation of the meaning of ： Not completely increasing , The value after the array will not be smaller than the value before .
 
And when the nums1 and nums2 After the merger , The same is Non decreasing order Array of ;
 
And it's about putting nums2 Merge into nums1 Medium , because num1 Have been to nums2 Opened space .

Train of thought

The first idea to be introduced today is Merger , First nums1 and nums2 The array is as follows

And then we use Subscripts act as pointers , The pointer i Point to nums1 The first element of , The pointer j Point to nums2 The first element of ;

Then open up a new array nums3, also nums3 The size and nums1 equally , And the pointer dst Point to nums3 The first element of ; As shown in the figure

First i The element pointed to is less than j Pointing elements , Then put i Put the smaller element pointed to num3 in , As shown in the figure

And then the pointer i and dst Move backward at the same time

next i And j The elements pointed to are equal , Then casually put one of the elements into nums3 in , Suppose that j Put in num3 in , As shown in the figure

Then put the pointer j and dst Move backward at the same time

next i The element pointed to is less than j Pointing elements , Then put i Put the smaller element pointed to num3 in , As shown in the figure

And then the pointer i and dst Move backward at the same time

next i The element pointed to is still less than j Pointing elements , Then put i Put the smaller element pointed to num3 in , As shown in the figure

And then the pointer i and dst Move backward at the same time

here nums1 The elements in have gone , So directly put nums2 Get the remaining elements in nums3 In the middle ;

The first j Pointing elements 5 Take it , then j and dst Move backward at the same time

Finally, put j Pointing elements 6 Take it

The idea is ： Compare in turn , Put the small ones into the merge array every time .

But the biggest problem with this method is ： You need to open an extra array , Then it does not meet the requirements of the topic

Train of thought two

The method of train of thought one is ： Traverse the array from left to right , Take a small value ;
 
Then I can choose From right to left Take the larger value , And then to get nums1 In the array , because nums1 The array has been opened up , There is room for them to merge ;

Or use it Subscripts act as pointers , The pointer i Point to nums1 The last It works Elements , The pointer j Point to nums2 The last It works Elements ; And then the pointer dst Point to nums1 Of The location of the last space ;

As shown in the figure

First j The element pointed to is greater than i Pointing elements , Then put j Put the element pointed to dst Point to the position , As shown in the figure

And then the pointer dst and j Move forward one bit at the same time （ Who points to the big element , The pointer is subtracted ）

next j The element pointed to is still greater than i Pointing elements , Then put j Put the element pointed to dst Point to the position , As shown in the figure

And then the pointer dst and j Move forward one bit at the same time

here i The element pointed to is greater than j Pointing elements , Then put i Put the element pointed to dst Point to the position , As shown in the figure

And then the pointer dst and i Move forward one bit at the same time

here i The element that points to is equal to j Pointing elements , Then just put an element into dst Point to the position ;

Assume that j Put the element pointed to , And then the pointer dst and j Move forward one bit at the same time

You can see the pointer at this time j Have the nums2 The elements in are traversed , Go further and form A cross-border visit 了 ;

So when j After traversing , And that's it ;

But there are also the following situations

because nums1 Each value in the array is greater than nums2 Of , So the pointer i I'm sure I'll put it in advance nums1 End of traversal , Then we need to put num2 Every element in gets nums1 Before 3 Take a seat

So the core is to see which array is traversed first ！

This method does not open up additional space , So the time complexity is $O(M+N)$
 
m by nums 1 Number of valid elements in ;
 
n by nums 2 Number of valid elements in .

3. Code implementation

Interface code

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    
    int i = m - 1;
    int j = n - 1;
    int dst = m + n - 1;
    // nums2  Finish first 
    while (i >= 0 && j >= 0) {
    
        if (nums1[i] > nums2[j]) {
    
            nums1[dst] = nums1[i];
            --dst;
            --i;
        }
        else {
    
            nums1[dst] = nums2[j];
            --dst;
            --j;
        }
    }
    
    // nums1  Finish first 
    while (j >= 0) {
    
        nums1[dst] = nums2[j];
        --dst;
        --j;
    }
}

In fact, it can be simplified again

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    
    int i = m - 1;
    int j = n - 1;
    int dst = m + n - 1;
    // nums2  Finish first 
    while (i >= 0 && j >= 0) {
    
        if (nums1[i] > nums2[j]) {
    
            nums1[dst--] = nums1[i--];
        }
        else {
    
            nums1[dst--] = nums2[j--];
        }
    }
    // nums1  Finish first 
    while (j >= 0) {
    
        nums1[dst--] = nums2[j--];
    }
}

Submit results