Leetcode Median of Two Sorted Arrays (java)

2018-06-18 03:02:08来源：未知阅读 ()

解法一：

import java.util.Arrays;
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //存储合并后的数组
        int[] nums3 = new int[nums1.length + nums2.length];
        for (int i = 0; i < nums3.length; i++) {
             if(i < nums1.length){
                 nums3[i] = nums1[i];
             }
             else {
                 nums3[i] = nums2[i-nums1.length];
             }
        }
        //进行升序排序
        Arrays.sort(nums3);
        //寻找median
        double median;
        if(nums3.length % 2 == 1){
             median = nums3[(nums3.length/2) ];
        }
        else{
             median = (nums3[((nums3.length/2))]+nums3[(nums3.length/2)-1])/2.0;
        }
        return median;
    }
}

该解法思路是把两个数组合并，进行升序排序，取中间值

解法二：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
       int n = nums1.length;
       int m = nums2.length;
       //让nums1始终最短
       //若num2比nums1长会出现数组越界问题
       if(n > m){
           return findMedianSortedArrays(nums2,nums1);
       }
       int l1;//nums1左部分最右的元素
       int r1;//nums1右部分最左的元素
       int c1;//nums1分割位置
       int l2;//nums2左部分最右的元素
       int r2;//nums2右部分最左的元素
       int c2;//nums2分割部分
        //让数组恒为奇数
       int start = 0;
       int end = 2 * n + 1 - 1;
       //开始不断分割nums1
       while (start <= end){
           //c1 c2保证了是前m+n个数 数组总长为2(m+n)
           c1 = (start + end) / 2;
           c2 = m + n - c1;

           l1 = c1 == 0 ? Integer.MIN_VALUE : nums1[(c1 - 1 ) / 2];
           r1 = c1 >= 2*n ? Integer.MAX_VALUE : nums1[(c1) / 2];

           l2 = c2 == 0 ? Integer.MIN_VALUE : nums2[(c2 - 1) / 2];
           r2 = c2 >= 2*m ? Integer.MAX_VALUE : nums2[(c2) / 2];

           //l1减少 r2增大
           if(l1 > r2){
               end = c1 - 1;
           }
           //r1增大 l2减少
           else if(l2 > r1){
               start = c1 + 1;
           }
           else {
               double median = ( Math.max(l1,l2) + Math.min(r1,r2) ) / 2.0;
               return median;
           }
       }
       return 0.0;
    }
}