Leetcode Median of Two Sorted Arrays (java)

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

新老客户大回馈,云服务器低至5折

解法一:

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;
    }
}

 该解法思路是:

  用两个分割位置把两个数组各自分成两部分,两个数组即是四部分,为l1,r1,l2,r2

  由于取的是中值,即是取第m+n个(这个做法是因为把数组长度都假设成了2*n + 1个来让数组为奇数个)

  分割的位置先是第一个数组的一半,第二个数组是 m+n - 第一个数组的位置,为了保证两个数组的左部分加起来个数是m+n来取到第m+n个数

  并且要保证两个左半部分要恒小于两个右半部分,即是l1<r1&&l1<r2 和 l2<r2&&l2<r1 因为已经是有序数组,所以有一半可以忽略,即是 l1<r2 && l2<r1

  若不满足上述条件,就把分割位置进行移动,此时正确的位置肯定在其中一边,把另一边舍去后继续二分直到符合上述条件

  当满足上述条件,l1和l2最大的,r1和r2最小的,它们的和除以2就可以得出答案

关于边界问题:

  只要保证nums1<=nums2即可,因为若出现nums1>nums2的时候,会出现nums2的分割位置出现数组越界的情况

 

github地址:https://github.com/CyanChan/leetcode

  

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:线程--实现Runnable接口

下一篇:数据库事务的四大特性以及事务的隔离级别