4.寻找两个有序数组的中位数/寻找两个有序数组的第K个数

2019-03-03  本文已影响0人  秋笙fine

思路:将两个数组merge成一个数组help,建立三个工作索引,两个工作索引分别指向nums1,nums2,值小的填入help中。直到遍历完两个数组。最后对长度的奇偶性作出判断求出中位数即可。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
          //这里用一部分归并排序思想
          int m=nums1.length;
          int n=nums2.length;
          int help[]=new int[m+n];
          int i=0,j=0,k=0;//工作索引,用来遍历数组
          while(i<m&&j<n){//遍历 将两个数组的数字填入
            help[k++]=nums1[i]<nums2[j]?nums1[i++]:nums2[j++];
          }
          //两个数组必有一个先填完越界
          while(i<m){//nums2填完
            help[k++]=nums1[i++];
          }
          while(j<n){//nums1填完
            help[k++]=nums2[j++];
          }
          //此时help数组就是将原数组排好序的数组,此时我们遍历help数组,找出中位数即可。
          double result;
          if(((m+n)&1)==1) result=help[(m+n)>>1];//长度为奇数则直接为中间索引
          else result=(help[(m+n)/2-1]+help[(m+n)>>1])*1.0/2;//长度为偶数,则中间索引-1和中间索引的中值
          return result;
    }
}
上一篇 下一篇

猜你喜欢

热点阅读