力扣刷题 -2020-07-13

曾经终败给现在 2023-02-26 07:27 10阅读 0赞

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

### 示例 1: ###

nums1 = [1, 3]
    nums2 = [2]
    
    则中位数是 2.0

### 示例 2: ###

nums1 = [1, 2]
    nums2 = [3, 4]
    
    则中位数是 (2 + 3)/2 = 2.5

解题思路：

1.  可能出现的情况：会有四种情况出现。两个都有值，两个都没值，nums1有值nums2无值，nums1无值nums2有值。四种情况
2.  我把int数组转化成了Integer数组，这样方便后面存入ArrayList数组中
3.  关键方法addAll，这里是把所有的数据都存进去，不考虑重复。
4.  两个if判断，一个是偶数情况下，取中间两个数就平均数（这里有人会问为啥是2.0。因为定义的类型是double,要不会出现精度问题。奇数情况下就是直接取中位数了。）。
5.  还有一个关键方法就是 Collections.sort(all);//排序，正向排序

给定两个数组，那么

class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
           ArrayList<Integer> all = new ArrayList<>();
            Integer[] newNum1=new Integer[nums1.length];
            for(int i= 0;i<nums1.length;i++){
                newNum1[i]=Integer.valueOf(nums1[i]);
            }
            Integer[] newNum2=new Integer[nums2.length];
            for(int i= 0;i<nums2.length;i++){
                newNum2[i]=Integer.valueOf(nums2[i]);
            }
            double zhong=1.0;
            if(newNum1.length>0){
                if(newNum2.length>0){//都大于零
                    all.addAll(0,Arrays.asList(newNum1));
                    all.addAll(0,Arrays.asList(newNum2));
                    Collections.sort(all);//排序
                    if(all.size()%2 == 0){
                        zhong=((all.get(all.size()/2)+(all.get(all.size()/2-1))))/2.0;
                    }else{
                        zhong=all.get((int)(all.size()/2+0.5));
                    }
                }else {//一大于零，二小于零
                    all.addAll(0,Arrays.asList(newNum1));
                    Collections.sort(all);
                    if(all.size()%2 == 0){
                        zhong=((all.get(all.size()/2)+(all.get(all.size()/2-1))))/2.0;
                    }else{
                        zhong=all.get((int)(all.size()/2+0.5));
                    }
                }
    
            }else{
                if(newNum2.length>0){//一小于零，二大于零
                    all.addAll(0,Arrays.asList(newNum2));
                    Collections.sort(all);
                    if(all.size()%2 == 0){
                        zhong=((all.get(all.size()/2)+(all.get(all.size()/2-1))))/2.0;
                    }else{
                        zhong=all.get((int)(all.size()/2+0.5));
                    }
                }else {//全小于零
    
                }
            }
            return zhong;
        }
    }