Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Replace array 2 with 0 in array 1, and.sort() sort. I’m the devil (Dog face)

— Leetcode

preface

This is a United States group side encountered the problem, belongs to the simple level.

Careful thinking and yesterday’s sliding window has the same wonderful!

Question

Difficulty: Medium

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
-109 <= nums1[i], nums2[i] <= 109
Copy the code

Solution

  • Define two Pointers to point tonums1andnums2The element.
  • Defines a pointer to a new array
  • Note:nums1.length == m + n , this information tells us that we don’t need to create an array,In situ modificationCan.
  • In order not to break the original array, from back to front traversal, compare and modify.

Code

/ * * *@author yitiaoIT
 */
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int indexM1=m-1;
        int indexN2=n-1;
        int index=m+n-1;
        while (indexN2>=0||indexM1>=0) {if (indexM1<=-1){
                nums1[index--]=nums2[indexN2--];
            }else if(indexN2<=-1){
                nums1[index--]=nums1[indexM1--];
            }else{ nums1[index--]=nums1[indexM1]>nums2[indexN2]? nums1[indexM1--]:nums2[indexN2--]; }}}}Copy the code

Result

Complexity analysis

  • Time complexity: O(Max (m,n))

I am a computer programmer in the Internet.

When the path is long and obstructed, it will come. Everyone’s praise, collection and attention is the biggest power of creation. See you next time!

Note: If you have any questions or suggestions about this blog, please leave comments!