LeetCode 题解4 寻找两个正序数组中的中位数 解法2

 

这里是暴力解法的优化   

有两个条件  第一数组是正序  第二找到中位数

中位数有两种  一  种是 当数组长度合为 奇数情况 找出 len/2位置的数即可

数组长度为偶数的情况时  则需找到 (( len/2)+(len/2)-1)/2.0           注 用数组总长度为3  和4 代入一下就理解了   

  //开始解答

  public double findMedianSortedArrays(int[] nums1, int[] nums2) {     //获取数组长度     int m  = nums1.length, n = nums2.length;     // 获取数组总长度     int len = m+n;     // 预设两个 容器   一个存 (len/2) -1  一个存 len/2 的值                int left = -1, right = -1;     //两个标记位      int mStart   = 0 , nStart = 0;     // 开始遍历  从倒数第一开始找  找到 倒数  第k个zhi     for (int i = 0; i<= len/2;i++){       // 每次开始  left 一致  结束时    只有right 改变  而left  就是  第 k-1 个值  也就是目标值的前一位       left = right;         // 我们现在只要判断如何移动标记位就可以了        //mStar<m   这是操作 num1 的先决条件  如果 违背  则 数组越界        //  nStart>=n  此时只能移动  num1  原因同上        //  移动标记位的第二个条件就是  num1 的值 比num2 的小   类似冒泡排序   我们这里每次找到一个最小 值  谁小谁先被排除  因为我们要找的是第k 小的值         if(mStart <m && ( nStart >=n || num1[mStart ]<num2[ nStart ]  ) ){             right = nums1[ mStart];         }else{             right = nums2[ nStart];          }     }       //  数字的奇偶性取决于最后一位   如果最后一位  为 0    0& 1 = 0  1 &1 = 1      if ((len&1) ==0)         return (left +right)/2.0;       else         return right;   }

 

上一篇:变量类型


下一篇:noip模拟13