merge

concept

What is merge? Merge is actually two steps, one is merge, and one is union. Grouping is the process of combining two and more ordered files, and grouping is the process of combining these groups into a new ordered file.

Sample analysis

Find the median of two positive ordinal groups. The problem is as follows: given two positive ordered (from smallest) arrays nums1 and nums2 of size m and n, respectively. Please find and return the median of the two positive ordinal groups.

So the idea here is pretty simple, you sort them, and then you look for the median, and there’s a bunch of ways to sort them, but I’m going to merge them.

Let’s take a look at the initial sorting process, I assume nums1 space is 5, nums2 space is 6, and then create a new num auxiliary space to use as the merged array.

The basic idea

Nums1 = {3, 5, 7, 8, 10}, nums2 = {4, 6, 8, 9, 11, 12}. Nums1 = 5; nums2 = 5; nums1 = 5; nums2 = 5 Nums [3] is the same as nums[2], but nums1 index is incremented. Until one array has been traversed, that is, when nums1’s subscript exceeds the length of the array, the value of another array is copied to NUMS, and finally the merge is complete. And then find the median.

The illustration

Specific code

class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int l1 = nums1.length; int l2 = nums2.length; int[] num = new int[l1 + l2]; Int I = 0; Int j = 0; Int k = 0; /*while(I < l1 &&j < l2){if(nums1[I] < nums2[j]){num[k] = nums1[I ++]; }else{ num[k] = nums2[j++]; } k++; }*/ for(i=0; i<l1&&j<l2; k++) { if(nums1[i] < nums2[j]){ num[k] = nums1[i++]; }else{ num[k] = nums2[j++]; If (I < l1){for (int a = I; a<l1; a++){ num[k++] = nums1[a]; } }else{ for (int a = j; a<l2; a++){ num[k++] = nums2[a]; Int y = num. Length % 2; int y = num. Length % 2; int y = num. Int c = num. Length / 2; if(y == 1){ return num[c]; }else{ return (double)(num[c] + num[c - 1])/2; }}}Copy the code

The code analysis

In simple terms, the code is divided into two phases, one for merging and one for finding the median.

Merge phase

The merge phase is the implementation of the above ideas, which can be implemented using either a for loop or a while loop.

Looking for the median

To find the median, you also need to judge whether it’s odd or even. And then we have to do our remainder rule, which is we take the remainder, if the remainder is 1, we take the middle element, and if the remainder is 0, we take two elements and divide by 2.

conclusion

Daily strength buckle, feel the code, learn methods, sum up experience.

Hope to help you with your study, thank you!