Given two positively ordered (from small to large) arrays nums1 and nums2 of size m and n, respectively. Find and return the median of the two ordinal groups, with order log (m+n) time

Input: nums1 = [1,3], nums2 = [2] output: 2.00000 explanation: merge array = [1,2,3], median 2Copy the code

Since the array may be even in length, the median may be the average of the two middle numbers, and the returned data may be decimal. So the data type is double, implemented in the Java language in this article

thinking

This problem in Letcode annotation difficulty is difficult, the reason is O(log (m+n)) time complexity

The first reaction is the same, you merge two ordered arrays, and you take the middle value, or the average of the two middle values, but it’s obviously not time complex.

When it comes to log level complexity, it’s easy to think about dichotomies, because that’s log level time, but if you think about it, the median of an ordered array, you can actually think of it as finding the KTH largest number

And it’s two ordered arrays, so you just take the median k1 and k2 for each array, and you compare them again, and you get the final result, for example

If m[1]>n[1], discard the first two digits of n, and k=5-2=3. If m[1]>n[1], discard the first two digits of n

In the second round, k=3,3/2=1, find the first number of each array (note that n should be the third number here, because the first two have been removed), and so on, and so on, finally k= 1, that is to say, we need to find the last smallest number to be the median, so that we can directly compare the size of m[I],n[j]

In the code

@test public void Test(int[] nums1, int[] nums2){@test public void Test(int[] nums2, int[] nums2){ Int left = (nums1.length+nums2.length+1)/2; int right = (nums1.length+nums2.length+2)/2; // There are even numbers and odd numbers, so calculate the average twice. For odd numbers, Return (getResult(nums1,0,nums1.length-1,nums2,0,nums2.length-1,left)+ GetResult (nums1, 0, nums1 length 1, nums2, 0, nums2. Length 1, right)) * 0.5; } public int getResult(int[]num1,int start1,int end1,int[] num2,int start2,int end2,int k){} public int getResult(int[] num2,int start2,int end2,int k) end1-start1+1; int len2 = end2-start2+1; / / here in order to avoid all kinds of judgment, directly through the judgment to ensure that the shortest num1 array, the if (len1 > len2) return getResult (num2, start2 end2, num1, start1, end1, k); If (len1==0) return num2[start2+k-1]; return num2[start2+k-1]; Return math.min (num1[start1],num2[start2]) if (k==1) return math.min (num1[start1],num2[start2]); Int I = start1+ math.min (len1,k/2)-1; int j = start2+Math.min(len2,k/2)-1; // Compare the values, recursively, to the top exit. if (num1[i]>num2[j]){ return getResult(num1,start1,end1,num2,j+1,end2,k-(j-start2+1)); }else{ return getResult(num1,i+1,end1,num2,start2,end2,k-(i-start1+1)); }}Copy the code