Shulou(Shulou.com)05/31 Report--

This article mainly explains "how C++ achieves the median of two ordered arrays". The explanation in the article is simple and clear and easy to learn and understand. let's study and learn how C++ achieves the median of two ordered arrays.

The median of two ordered arrays

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

This problem allows us to find the median of two ordered arrays, and limits the time complexity to O (log (massin)). Seeing this time complexity, we naturally think that we should use the binary search method to solve it. But there is a reason why this problem is defined as Hard. It is difficult to use dichotomy between two unmerged ordered arrays. If the problem has only one ordered array, it is probably an Easy problem. For this problem, can you mix two ordered arrays into an ordered array? it's too young and easy, and the time complexity is limited by telling you not to think about it. You still have to use dichotomy, and it's used between two arrays, which feels very high-end. Looking back at the definition of the median, if the length of an ordered array is odd, then the median is the middle one, and if it is even, it is the average of the two middle numbers. The same is true for two ordered arrays, assuming that the lengths of the two ordered arrays are m and n respectively. Because the sum of the lengths of the two arrays is odd and even, it needs to be discussed separately. In the case of odd numbers, you can find the middle number directly, and even numbers require the average of the two middle numbers. In order to simplify the code, regardless of the situation, use a small trick, find (m+n+1) / 2, and (m+n+2) / 2 respectively, and then find their average, which is applicable to both odd and even numbers. If m _ n is odd, then the values of (m+n+1) / 2 and (m+n+2) / 2 are equal, which is equivalent to the addition and division of two identical numbers by 2, or itself.

OK, here we need to define a function to find the Kth element in the two ordered arrays. Let's focus on how to find the Kth element. First of all, in order to prevent the copy from generating a new array and increase the time complexity, two variables I and j are used to mark the starting position of the array nums1 and nums2, respectively. Then deal with some corner cases, for example, when the starting position of an array is greater than or equal to its array length, it means that all its numbers have been eliminated, equivalent to an empty array, then it actually becomes looking for numbers in another array and can be found directly. And if you want to use knot 1, just compare the numbers on the starting positions I and j of nums1 and nums2. The difficulty is how to deal with the general situation. Because you need to find the Kth element in two ordered arrays, in order to speed up the search, you can use dichotomy, so who is dichotomized, the array? In fact, if you want to dichotomy K, it means that you need to look up the 2 elements of Kmax in nums1 and nums2 respectively. Note here that because the length of the two arrays is uncertain, it is possible that some array does not have the 2nd number of KUnip, so you need to check first to see whether there is the 2nd number in the array. If so, take it out. Otherwise, the last integer maximum is assigned (the purpose is to eliminate the two smaller numbers of midVal1 or nums2 first in midVal1 or midVal2, and the judgment is based on which one is smaller, but if the number of an array is less than 2, it will not be eliminated, so the corresponding midVal value is set to the maximum integer value to ensure that it will not be eliminated). If an array does not have the 2nd number of Kbig, it cannot be eliminated. You can eliminate the first 2 digits of another array. For example, nums1 = {3}, nums2 = {2, 4, 5, 6, 7}, Know4. If you want to find the fourth number in the mixture of two arrays, find the second number in nums1 and nums2 respectively, while there is only one number in nums1, and there is no second number, then the first two digits in nums2 can be skipped directly, because what is required is the fourth number of the whole mixed array. No matter which number in nums1 is large or small, the fourth number will never appear in the first two digits of nums2, so you can just skip it.

Is it possible that there is no second number in both arrays? it is impossible in this question, because K is not given arbitrarily, but the middle value of the given mendn, so there must be at least one array that has the second number. Finally, there is the core of dichotomy. Compare the size of the small numbers midVal1 and midVal2 of the KUniver 2 of the two arrays. If the second digit of the first array is small, then it means that the number you are looking for is definitely not in the first 2 digits of the nums1, which can be eliminated, and the starting position of the nums1 can be moved backward by 2 Kcanes. At this time, K is also subtracted from KThan2, calling recursion, for example. For example, nums1 = {1,3}, nums2 = {2,4,5}, Kraft 4, if you want to find the fourth number in the mixture of two arrays, then find the second number in nums1 and nums2 respectively. The second number in nums1 is 3, and the second number in nums1 is 4. Because 3 is less than 4, the fourth number in the mixed array must be in nums2, and you can move the starting position of nums1 backwards by 2 digits. On the contrary, eliminate the first 2 digits in nums2, and move the starting position of nums2 backward by 2 numbers, and the K at this time also subtracts it from itself. Just call recursion, as shown in the code below:

C++ solution one:

Class Solution {public: double findMedianSortedArrays (vector& nums1, vector& nums2) {int m = nums1.size (), n = nums2.size (), left = (m + n + 1) / 2, right = (m + n + 2) / 2; return (findKth (nums1, 0, nums2, 0, left) + findKth (nums1, 0, nums2, 0, right)) / 2.0 } int findKth (vector& nums1, int I, vector& nums2, int j, int k) {if (I > = nums1.size ()) return nums2 [j + k-1]; if (j > = nums2.size ()) return nums1 [I + k-1]; if (k = = 1) return min (nums1 [I], nums2 [j]); int midVal1 = (I + k / 2-1)

< nums1.size()) ? nums1[i + k / 2 - 1] : INT_MAX; int midVal2 = (j + k / 2 - 1 < nums2.size()) ? nums2[j + k / 2 - 1] : INT_MAX; if (midVal1 < midVal2) { return findKth(nums1, i + k / 2, nums2, j, k - k / 2); } else { return findKth(nums1, i, nums2, j + k / 2, k - k / 2); } }}; Java 解法一： public class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length, left = (m + n + 1) / 2, right = (m + n + 2) / 2; return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0; } int findKth(int[] nums1, int i, int[] nums2, int j, int k) { if (i >

= nums1.length) return nums2 [j + k-1]; if (j > = nums2.length) return nums1 [I + k-1]; if (k = = 1) return Math.min (nums1 [I], nums2 [j]); int midVal1 = (I + k / 2-1)

< nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE; int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE; if (midVal1 < midVal2) { return findKth(nums1, i + k / 2, nums2, j, k - k / 2); } else { return findKth(nums1, i, nums2, j + k / 2, k - k / 2); } }} 上面的解法一直使用的是原数组，同时用了两个变量来分别标记当前的起始位置。我们也可以直接生成新的数组，这样就不要用起始位置变量了，不过拷贝数组的操作可能会增加时间复杂度，也许会超出限制，不过就算当个思路拓展也是极好的。首先要判断数组是否为空，为空的话，直接在另一个数组找第K个即可。还有一种情况是当 K = 1 时，表示要找第一个元素，只要比较两个数组的第一个元素，返回较小的那个即可。这里分别取出两个数组的第 K/2 个数字的位置坐标i和j，为了避免数组没有第 K/2 个数组的情况，每次都和数组长度做比较，取出较小值。这里跟上面的解法有些许不同，上面解法直接取出的是值，而这里取出的是位置坐标，但是思想都是很类似的。不同在于，上面解法中每次固定淘汰 K/2 个数字，而这里由于取出了合法的i和j，所以每次淘汰i或j个。评论区有网友提出，可以让 j = k-i，这样也是对的，可能还更好一些，收敛速度可能会更快一些，参见代码如下： C++ 解法二： class Solution {public: double findMedianSortedArrays(vector& nums1, vector& nums2) { int m = nums1.size(), n = nums2.size(); return (findKth(nums1, nums2, (m + n + 1) / 2) + findKth(nums1, nums2, (m + n + 2) / 2)) / 2.0; } int findKth(vector nums1, vector nums2, int k) { if (nums1.empty()) return nums2[k - 1]; if (nums2.empty()) return nums1[k - 1]; if (k == 1) return min(nums1[0], nums2[0]); int i = min((int)nums1.size(), k / 2), j = min((int)nums2.size(), k / 2); if (nums1[i - 1] >

Nums2 [j-1]) {return findKth (nums1, vector (nums2.begin () + j, nums2.end ()), k-j);} else {return findKth (vector (nums1.begin () + I, nums1.end ()), nums2, k-I);} return 0;}}

Java solution II:

Public class Solution {public double findMedianSortedArrays (int [] nums1, int [] nums2) {int m = nums1.length, n = nums2.length, left = (m + n + 1) / 2, right = (m + n + 2) / 2; return (findKth (nums1, nums2, left) + findKth (nums1, nums2, right)) / 2.0 } int findKth (int [] nums1, int [] nums2, int k) {int m = nums1.length, n = nums2.length; if (m = = 0) return nums2 [k-1]; if (n = = 0) return nums1 [k-1]; if (k = = 1) return Math.min (nums1 [0], nums2 [0]) Int I = Math.min (m, k / 2), j = Math.min (n, k / 2); if (nums1 [I-1] > nums2 [j-1]) {return findKth (nums1, Arrays.copyOfRange (nums2, j, n), k-j);} else {return findKth (Arrays.copyOfRange (nums1, I, m), nums2, k-I);}

This problem can also be solved by iterative binary search method, which is a quite ingenious application. Let's refer to stellari's post to explain it. The so-called median, from another point of view, is actually dividing an ordered array into two segments of equal length. The median is the average of the maximum value of the first half and the minimum value of the second half, that is, the average of the two numbers adjacent to the division point. For example, for even arrays [1 357], then the split is [13 / 57], where'/ 'represents the partition point, and the median is the average of 3 and 5. For an odd array [1 345 7], it can be divided into [1 34 / 4 57], and it can be found that there is a 4 on both sides, then the median is the average of two 4, or 4. Here L is used to denote the number to the left of the partition point, and R is the number to the right of the partition point, then for [1 357], Lemma 3 ~ 5 is used. For [1, 3, 4, 5, 7], Lind4 is not the same as Renew4. Then for an array of length N, you can get the positions of L and R, respectively, as follows:

N Index of L Index of R

1 0 0

2 0 1

3 1 1

4 1 2

5 2 2

6 2 3

7 3 3

If you look at the table above, you can get the rule: Idx (L) = (NMUI 1) / 2 Magi IDX (R) = Nmax 2, so the median can be expressed by the following expression:

(l + R) / 2 = (A [(N-1) / 2] + A [N / 2]) / 2

To unify the odd and even length of the array, you can use a small tricky, which adds a special character, such as a pound sign, to both sides of each number, which is actually used in the horse-drawn cart algorithm. The advantage of this is that whether odd or even, the length of the array after adding the pound sign is odd, and the position of the cutting point is also determined, such as:

[1 357]-> [# 1 # 3 # 5 # 7 #] N = 4

Index 0 1 2 3 4 5 6 7 8 newN = 9

[1 3 4 5 7]-> [# 1 # 3 # 4 # 5 # 7 #] N = 5

Index 0 1 2 3 4 5 6 7 8 9 10 newN = 11

N here is the length of the original array, newN is the length of the new array after adding the pound sign, you can find newN = 2N+1, and the cutting point is always in the position where the coordinates of N are in the new array, and idx (L) = (NRIC1) / 2Lignidx (R) = NP2, the N here can be changed into the position of the split point, isn't it beautiful (note that idx (L) and idx (R) here represent the coordinate position that is not filled with #)! Now suppose there are two arrays:

[1 3 4 5 7]-> [# 1 # 3 # 4 # 5 # 7 #] N1 = 5

Index 0 1 2 3 4 5 6 7 8 9 10 newN1 = 11

[1 2 22]-> [# 1 # 2 # 2 # 2 #] N2 = 4

Index 0 1 2 3 4 5 6 7 8 newN2 = 9

Similar to the case where there is only one array, we need to find a cut point so that it can divide the two arrays into left and right parts respectively. What needs to be satisfied is that either of the two left half numbers is less than the number of the two right half arrays. Note that the left or right half that may be here will be empty, but the sum of the two left half numbers should be equal to the sum of the two right half numbers. Some rules can also be observed here:

1. There are a total of 2N1 + 2N2 + 2 positions, so excluding the two split points, there should be N1 + N2 digits on each of the left and right halves.

two。 Therefore, for a partition point position C2 = K in the A2 array, the position in the A1 array should be C1 = N1 + N2-K, for example, if the partition point position in A2 is C2 = 2, then the position in A1 is C1 = 4 + 5-C2 = 7.

[# 1 # 3 # 4 # (5Accord 5) # 7 #]

[# 1 / 2 # 2 # 2 #]

3. If both arrays are split, there should be two L and R, which are:

L1 = A1 [(C1-1) / 2]

R1 = A1 [C1 / 2]

L2 = A2 [(C2-1) / 2]

R2 = A2 [C2 / 2]

For the above example, there are:

L1 = A1 [(7-1) / 2] = A1 [3] = 5

R1 = A1 [7 / 2] = A1 [3] = 5

L2 = A2 [(2-1) / 2] = A2 [0] = 1

R2 = A2 [2 / 2] = A2 [1] = 2

Now we need to check whether this cut point is the correct median cut point, then according to the previous analysis, any number on the left side needs to be less than or equal to the number on the right side, L1 and L2 are the largest numbers on the left side, and R1 and R2 are the smallest numbers on the right side, so the following relations need to be satisfied:

L1

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.