This is the sixth day of my participation in the November Gwen Challenge. See details: The Last Gwen Challenge 2021.

Cleverly merge two ordered arrays using two solutions

Topic describes

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.

The subject sample

The title method

Solution one: Based on Java native sorting algorithm

Use Java’s own sorting algorithm

/** * + array.sort () */ class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) { int firstLenth = nums1.length; if(n == 0){ return; } int nextIndex = firstLenth - n; For (int I = 0; i < n; i++){ nums1[nextIndex+i] = nums2[i]; } arrays.sort (nums1); }}Copy the code

Solution two: double pointer reverse reorganization

Dynamic identification pointer, complete reorganization and sorting

Public void merge(int[] nums1, int m, int n) {int last = m + n-1; int firtLast = m - 1; int secondLast = n - 1; while(secondLast >= 0){ int curMax; int secondMax = nums2[secondLast]; if(firtLast >= 0 && nums1[firtLast] > secondMax){ curMax = nums1[firtLast--]; }else { curMax = secondMax; secondLast--; } // nums1[last--] = curMax; }}}Copy the code

LeetCode: leetcode-cn.com/problems/me…