categories: leetcode

2..png

题目描述

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

参考代码

  1. class Solution {
  2.     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
  3.         int m = nums1.length;
  4.         int n = nums2.length;
  5.         if (m > n) {
  6.             int[] tmp = nums1; nums1 = nums2; nums2 = tmp;
  7.             int temp = m; m = n; n = temp;
  8.         }
  9.         int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
  10.         while (iMin <= iMax) {
  11.             int i = (iMin + iMax) / 2;
  12.             int j = halfLen - i;
  13.             if (i < iMax && nums2[j-1] > nums1[i]) {
  14.                 iMin = i + 1;
  15.             }
  16.             else if (i > iMin && nums1[i-1] > nums2[j]) {
  17.                 iMax = i - 1;
  18.             }
  19.             else {
  20.                 int maxLeft = 0;
  21.                 if (i == 0) { maxLeft = nums2[j-1];}
  22.                 else if (j == 0) {maxLeft = nums1[i-1];}
  23.                 else { maxLeft = Math.max(nums1[i-1], nums2[j-1]); }
  24.                 if ( (m + n) % 2 == 1) { return maxLeft; }
  26.                 int minRight = 0;
  27.                 if (i == m) { minRight = nums2[j]; }
  28.                 else if (j == n) {minRight = nums1[i]; }
  29.                 else { minRight = Math.min(nums2[j], nums1[i]); }
  31.                 return (maxLeft + minRight) / 2.0;
  32.             }
  33.         }
  34.         return 0.0;
  35.     }
  36. }

思路及总结

当找到目标对象 ii时，中位数为：
4. Median of Two Sorted Arrays - 图2
4. Median of Two Sorted Arrays - 图3
当为奇数时，left的数字较多，可以举例来理解一下
4. Median of Two Sorted Arrays - 图4 保证奇偶都能满足
最后的那个数学证明是看到头都大了，大概是那个道理。还是官方解答，最为致命。时间复杂度为log(m+n),意思就是只能单层循环一次两个数组，有点利用二分法和分治的思想。

参考

https://leetcode.com/problems/median-of-two-sorted-arrays/solution/