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
第一种方法：只讨论m + n 为奇数的情况（偶数基本相同），则我们要找出一个数v满足在nums1,nums2 所有比v小的个数为less_num =(m + n + 1) / 2 个， 设start1, end1为nums1 需要考察的区间
start2, end2为nums2需要考察的区间， 每次考察（end1 - start1 + 1） = （end2 - start2 + 1) = ceil(less_num / 2).如果nums1[end1] < nums2[end2] 则 我们要的值不可能出现在
nums1区间[start1, end1]中, 更新less_num -= (end - start + 1)， start1 = end1 + 1， end1 = start1 + ceil(less_num / 2) - 1, start2 不变，
end2 = start2 + ceil(less_num / 2) - 1. 以此类推nums2[end2] < nums1[end1]的情况， 每次less_num都减半,直到less_num = 0找到所求, 时间复杂度为o(log(m + n))
1 class Solution { 2 3 public double findMedianSortedArrays(int[] nums1, int[] nums2) { 4 int m = nums1.length, n = nums2.length; 5 int mid = (m + n) / 2 + (m + n) % 2; 6 int pos1 = -1, pos2 = -1; 7 while (mid > 0) { 8 int temp = mid / 2 + mid % 2; 9 if (pos2 + temp >= n || 10 (pos1 + temp < m && nums1[pos1 + temp] < nums2[pos2 + temp])) { 11 pos1 += temp; 12 } else { 13 pos2 += temp; 14 } 15 mid -= temp; 16 } 17 18 19 20 double ans = 0; 21 if (pos2 == -1 || (pos1 != -1 && nums1[pos1] >= nums2[pos2])) { 22 ans = nums1[pos1]; 23 } else { 24 ans = nums2[pos2]; 25 } 26 if ((m + n) % 2 == 0) { 27 double temp; 28 if (pos2 + 1 >= n || 29 (pos1 + 1 < m && nums1[pos1 + 1] < nums2[pos2 + 1])) 30 temp = nums1[pos1 + 1]; 31 else { 32 temp = nums2[pos2 + 1]; 33 } 34 ans = (ans + temp) / 2 ; 35 } 36 return ans; 37 38 } 39 }
第二种方法为solution中的做法，我就简单用自己的语言说说
首先把两个数组分成两个集合
left_part | right_part
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
假设m + n 是偶数，我们的目标就是找出满足 i + j = m - i + n - j（即两个集合元素个数相同）， left_part最大的元素maxleft <= minright(right_part最小的元素）的 i 和 j，
找出以后 求出maxleft 和minright (maxleft + minright) / 2 为所求中位数
下面两份代码，第一份是自己看一遍题解写出的代码，第二份是学习题解代码写的代码。1 class Solution { 2 3 public double findMedianSortedArrays(int[] nums1, int[] nums2) { 4 if (nums1.length > nums2.length) { 5 int []temp = nums1; 6 nums1 = nums2; 7 nums2 = temp; 8 } 9 10 int m = nums1.length, n = nums2.length; 11 if (m == 0) { 12 if (n % 2 == 1) { 13 return nums2[n / 2]; 14 } else { 15 return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0; 16 } 17 } 18 int l = 0, r = m, i = 0, j; 19 while (l < r) { 20 i = (l + r) / 2; 21 j = (m + n) / 2 - i; 22 23 if (i < m && nums2[j - 1] > nums1[i]) { 24 l = i + 1; 25 i = i + 1; 26 continue; 27 } 28 if (i > 0 && nums1[i - 1] > nums2[j]) { 29 r = i - 1; 30 i = i - 1; 31 continue; 32 } 33 break; 34 } 35 36 j = (m + n) / 2 - i; 37 double ans = 0; 38 if ((m + n) % 2 == 1) { 39 if (i == m) { 40 ans = nums2[j]; 41 } else if (j == n) { 42 ans = nums1[i]; 43 } else { 44 ans = Math.min(nums1[i], nums2[j]); 45 } 46 47 } else { 48 System.out.println(i); 49 if (i == 0) { 50 if (j == n) ans = (nums2[j - 1] + nums1[i]) / 2.0; 51 else ans = (nums2[j - 1] + Math.min(nums1[i], nums2[j])) / 2.0 ; 52 } else if (j == 0) { 53 System.out.println((nums1[i - 1] + nums2[j]) / 2.0); 54 if (i == m) ans = (nums1[i - 1] + nums2[j]) / 2.0; 55 else ans = (nums1[i - 1] + Math.min(nums1[i], nums2[j])) / 2.0; 56 } else { 57 ans = Math.max(nums1[i - 1], nums2[j - 1]); 58 double temp; 59 if (i == m) { 60 temp = nums2[j]; 61 } else if (j == n) { 62 temp = nums1[i]; 63 } else { 64 temp = Math.min(nums1[i], nums2[j]); 65 } 66 ans = (ans + temp) / 2.0; 67 } 68 } 69 return ans; 70 71 } 72 }
1 class Solution { 2 3 public double findMedianSortedArrays(int[] nums1, int[] nums2) { 4 if (nums1.length > nums2.length) { 5 int []temp = nums1; 6 nums1 = nums2; 7 nums2 = temp; 8 } 9 10 int m = nums1.length, n = nums2.length; 11 12 int l = 0, r = m, i = 0, j; 13 while (l <= r) { 14 i = (l + r) / 2; 15 j = (m + n) / 2 - i; 16 17 if (i < r && nums2[j - 1] > nums1[i]) { 18 l = i + 1; 19 20 } else if (i > l && nums1[i - 1] > nums2[j]) { 21 r = i - 1; 22 23 } else { 24 25 int minright = 0; 26 if (i == m) { 27 minright = nums2[j]; 28 } else if (j == n) { 29 minright = nums1[i]; 30 } else { 31 minright = Math.min(nums1[i], nums2[j]); 32 } 33 if ((m + n) % 2 == 1) return minright; 34 35 int maxleft = 0; 36 if (i == 0) { 37 38 maxleft = nums2[j - 1]; 39 } else if (j == 0) { 40 maxleft = nums1[i - 1]; 41 } else { 42 43 maxleft = Math.max(nums1[i - 1], nums2[j - 1]); 44 } 45 46 return (maxleft + minright) / 2.0; 47 } 48 49 } 50 51 return 0.0; 52 53 54 55 56 57 } 58 }