题目

image.png

思路

  • 思路一：直接一次循环遍历找到中位数

  • 思路二：使用二分法找到中位数

    代码

    1.    //1.直接一次遍历找到中位数
    2.   public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    3.       int m = nums1.length;
    4.       int n = nums2.length;
    5.       int mid = (m + n) / 2;
    6.       int i = 0, j = 0, l = 0, r = 0;
    7.       for (int k = 0 ; k <= mid; k++) {
    8.           l = r;
    9.           if (j >= n || i < m && nums1[i] < nums2[j]) {
    10.               r = nums1[i++];
    11.           } else {
    12.               r = nums2[j++];
    13.           }
    14.       }
    15.       if ((m + n) % 2 == 0) {
    16.           return (l + r) / 2.0;
    17.       } else {
    18.           return r;
    19.       }
    20.   }
    22.   //2. 二分法找到中位数
    23.   public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    24.       int m = nums1.length;
    25.       int n = nums2.length;
    26.       int left = (m + n + 1) / 2;
    27.       int right = (m + n + 2) / 2; 
    28.       return (find(nums1, 0, nums2, 0, left) + find(nums1, 0, nums2, 0, right)) / 2.0; 
    29.   }
    31.   public int find(int[] nums1, int i, int[] nums2, int j, int k) {
    32.       if (i >= nums1.length) return nums2[j + k - 1]; 
    33.       if (j >= nums2.length) return nums1[i + k - 1];
    34.       if (k == 1) return Math.min(nums1[i], nums2[j]);
    35.       int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
    36.       int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
    37.       if (midVal1 < midVal2)
    38.           return find(nums1, i + k / 2, nums2, j, k - k / 2);
    39.       else 
    40.           return find(nums1, i, nums2, j + k / 2, k - k / 2);
    41.   }

    寻找两个正序数组的中位数