题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。

示例 1： :::info 输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2 ::: 示例 2： :::info 输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5 :::
提示：

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

题解一：

使用四指针动态的从两头去遍历两个数组，保证两遍的步数一直，最后的值则为中位数

  1. class Solution {
  2.     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
  3.         // System.out.println("nums1:" + nums1[0]);
  4.         // System.out.println("nums2:" + nums2[0]);
  6.         int m = nums1.length;
  7.         int n = nums2.length;
  9.         boolean isEvenNumber = (m + n) % 2 == 0;
  10.         int left = (m + n) / 2;
  11.         int right = left;
  13.         int index1Prefix = 0;
  14.         int index1Suffix = m - 1;
  16.         int index2Prefix = 0;
  17.         int index2Suffix = n - 1;
  19.         System.out.println("index1Prefix:" + index1Prefix);
  20.         System.out.println("index2Prefix:" + index2Prefix);
  22.         System.out.println("index1Suffix:" + index1Suffix);
  23.         System.out.println("index2Suffix:" + index2Suffix);
  25.         System.out.println("left:" + left);
  26.         System.out.println("right:" + right);
  29.         //最后一次操作的指针
  30.         int lastPrefix = 0;
  31.         int lastSuffix = 0;
  33.         while (left > 0 || right > 0) {
  34.             if(left > 0){
  35.                 if(index1Prefix >= m || m == 0){
  36.                     index2Prefix += 1;
  37.                     lastPrefix = 2;
  38.                 }else if(index2Prefix >= n || n == 0){
  39.                     index1Prefix += 1;
  40.                     lastPrefix = 1;
  41.                 }else if (nums1[index1Prefix] < nums2[index2Prefix]) {
  42.                     index1Prefix += 1;
  43.                     lastPrefix = 1;
  44.                 } else {
  45.                     index2Prefix += 1;
  46.                     lastPrefix = 2;
  47.                 }
  48.                 left -= 1;
  49.             }
  51.             if(right > 0){
  52.                 if(index1Suffix < 0  || m == 0){
  53.                     index2Suffix -= 1; 
  54.                     lastSuffix = 2;
  55.                 }else if(index2Suffix < 0 || n == 0){
  56.                     index1Suffix -= 1;
  57.                     lastSuffix = 1;
  58.                 }else if (nums1[index1Suffix] > nums2[index2Suffix]) {
  59.                     index1Suffix -= 1;
  60.                     lastSuffix = 1;
  61.                 } else {
  62.                     index2Suffix -= 1; 
  63.                     lastSuffix = 2;
  64.                 }
  65.                 right -= 1;
  66.             }
  69.         System.out.println("--------");
  70.         System.out.println("index1Prefix:" + index1Prefix);
  71.         System.out.println("index2Prefix:" + index2Prefix);
  73.         System.out.println("index1Suffix:" + index1Suffix);
  74.         System.out.println("index2Suffix:" + index2Suffix);
  75.         }
  77.         System.out.println("isEvenNumber:" + isEvenNumber);
  78.         System.out.println("lastPrefix:" + lastPrefix);
  79.         System.out.println("lastSuffix:" + lastSuffix);
  81.         // System.out.println("left:" + left);
  82.         // System.out.println("right:" + right);
  85.         if(isEvenNumber){
  86.             //偶数判断，中位数需要判断，最后两个值。
  87.             int leftValue = lastPrefix == 1 ? nums1[index1Prefix - 1] : nums2[index2Prefix - 1];
  88.             int rightValue = lastSuffix == 1 ? nums1[index1Suffix + 1] : nums2[index2Suffix + 1];
  90.             return Double.valueOf(String.valueOf(leftValue + rightValue)) / 2;
  91.         }else{
  92.             //奇数，中位数还在数组中。
  93.             if(index1Prefix == index1Suffix){
  94.                 return Double.valueOf(String.valueOf(nums1[index1Prefix]));
  95.             }
  96.             return Double.valueOf(String.valueOf(nums2[index2Prefix]));
  97.         }
  98.     }
  99. }