concept

In computer science, divide-and-conquer is an important algorithm paradigm based on multinomial branch recursion. The literal interpretation is “divide and conquer”, which is to divide a complex problem into two or more identical or similar sub-problems until the sub-problems can be solved simply and directly, and the solution of the original problem is the combination of the solutions of the sub-problems.

The original problem

4. Median of Two Sorted Arrays （Hard)

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3] nums2 = [2]

The median is 2.0 Example 2:

nums1 = [1, 2] nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

4. Median of two ordered arrays (difficulty)

Given two ordered arrays nums1 and nums2 of size m and n.

Find the median of the two ordered arrays and the algorithm has order (log(m + n)) time.

You can assume that nums1 and nums2 are not null at the same time.

Example 1:

nums1 = [1, 3] nums2 = [2]

The median is 2.0.

nums1 = [1, 2] nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

  • This topic is under the divide and conquer classification in LeetCode

Analysis of the question

Two ordered arrays search for the median, which naturally can be associated with the simplest ordered array merge. But merging ordered arrays to find the median will obviously exceed O(log(m + n)), but according to the complexity requirements of the problem O(log(m + n)) can obviously think of the problem solution must be related to the idea of divide-and-conquer algorithm, because only the algorithm complexity of divide-and-conquer can reach the log level.

Concept design

Because the problem is to find the median, the solution must belong to divide and conquer, can use dichotomy. If you want to find out the first number k in two arrays all number, elimination method can be used, before each take two of the array number k / 2, compare two array number it is concluded that the smaller the first k / 2 a, can be eliminated before the decimal place array k / 2 all the Numbers, then get out two new array recursive cycle Finally find the first k until the cumulative number. For example, suppose there are two arrays M and n of length 5 and 10 respectively. Since we’re looking for the median, the sum len=5+10=15 is odd, and the median is exactly the eighth number, k is 8.

1, k = 8, k/2 = 4, eliminate 4;

For the first time, take the first k/2 = 4 number of A and B respectively. As shown in the figure above, since the fourth digit 4 in array B is smaller than the fourth digit 11 in array A, the first four digits of array B are eliminated and A new array is obtained to continue the comparison. Since the total number has been dropped by 4, the new k is 8 minus 4=4.

2, k = 4, k/2 = 2, then eliminate 2;

For the second time, take the first k/2 = 2 number of A and B respectively. As shown in the figure above, since the second digit 4 in array A is less than the second digit 6 in array B, the first two digits of array A are eliminated and A new array is obtained to continue the comparison. And since we’ve discarded 2 of the total, we get 4 minus 2 equals 2.

3, k= 2, k/2 = 1, then eliminate 1;

For the third time, take the first k/2 =1 number of A and B respectively, as shown in the figure above, since the first digit 5 in array A is equal to the first digit 5 in array B, the first digit of array A is still eliminated. At this time, k is 1, and the total number has been discarded to get A new k digit 2-1=1.

4. When k=1, it reaches the 8th position and ends the cycle

The last time we looked for the 8th digit, so we only need to compare the first digit of the new array A and B to get A smaller number. Since the first digit of array B, 5, is less than the first digit of array A, 5 is the median of the final two arrays.

A special case

  • If the sum is even, there must be two medians, the KTH and the k+1 number (bits k and k+1 indicate relative order in the total group).
  • If the length of the shorter array A in array A and array B is less than k/2, in order to prevent the array from crossing the boundary, array A is eliminated directly, and the value of the new k in the next round is changed to k-A.length.

Pseudo code

Find the median of two arrays (findMedia Sortedarrays method)1According to len1 and len2 of nums1, the median k is obtained;2I. If the total length of two arrays is odd and there is only one median integer, call method 2 directly to return the KTH bit of the two arrays; Ii. If the total length of two arrays is even, there are two median integers, which are the k and the k+1Bit, calling method two passing in k, k+1To calculate2Median integer average yields median; Find the KTH integer of two ordered arrays by starting position, k value (numberK)1According to the starting position and length of the two arrays, the effective length of the current array len1, len2;2, ensure that the array with small valid length is in front;3, special cases, when Len1 is0If the first valid array is empty, the first valid array is returned2The KTH bit integer (relative to the starting position) of the array;4, special case handling, when both arrays are only1The smaller integer is returned directly.5According to the starting position, array length and k value, calculate the subscript of the KTH number relative to the starting position of the two arrays respectively. Note that when the array length is less than k, special processing moves the subscript to the last bit of the array;6, compare the size of the KTH number of the two arrays: I. if the2If the KTH number of the array is small, move the th2Pointer to the array, k bits relative to the starting position, equivalent to the elimination of the first2K number of arrays, continue recursive calls; Ii. If otherwise1If the KTH number of the array is small, move the th1The number pointer, relative to the starting position k bits, is equivalent to the elimination th1K number of arrays, continue recursive calls;Copy the code

Coding practices

	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		int len1 = nums1.length;
		int len2 = nums2.length;
		int k = (len1 + len2 + 1) / 2;
		if (((len1 + len2) & 1) = =1) {
			return numberK(nums1, 0, nums2, 0, k);
		} else {
			return (numberK(nums1, 0, nums2, 0, k) + numberK(nums1, 0, nums2, 0, k + 1)) * 0.5; }}private int numberK(int[] n1, int start1, int[] n2, int start2, int k) {
		int len1 = n1.length - start1;
		int len2 = n2.length - start2;
		if (len1 > len2) {
			return numberK(n2, start2, n1, start1, k);
		}
		if (len1 == 0) {
			return n2[start2 + k - 1];
		}
		if (k == 1) {
			return Math.min(n1[start1], n2[start2]);
		}
		int end1 = start1 + Math.min(len1, k / 2) - 1;
		int end2 = start2 + Math.min(len2, k / 2) - 1;
		if (n1[end1] > n2[end2]) {
			return numberK(n1, start1, n2, end2 + 1, k - (end2 - start2 + 1));
		} else {
			return numberK(n1, end1 + 1, n2, start2, k - (end1 - start1 + 1)); }}Copy the code

## Conclusion This topic belongs to the classic divide-and-conquer idea. The dichotomy type in the divide-and-conquer idea belongs to the difficult type in Leetcode. It mainly investigates the design of divide-and-conquer idea and optimization of algorithm complexity. Finally, if you find this article helpful or inspiring, give it a thumbs up