在两个长度相等的排序数组中找到上中位数

红太狼 2022-05-26 00:44 149阅读 0赞

![这里写图片描述][70]

import java.util.*;
    //在两个长度相等的排序数组中找到上中位数
    public class FindShangMidNum{
    
        //找到两个数组的上中位数
        public static int getShangMidNum(int[]arr1,int[]arr2)
        {
            if((arr1==null&&arr2==null)||(arr1.length==0&&arr2.length==0)){
                 throw new RuntimeException("Your arr is invalid!");
            }else if(arr1==null||arr1.length==0){
                int temp=0;
                if((arr2.length&1)==0) //偶数
                {
                    temp=arr2[arr2.length/2-1];
                }else{
                    temp=arr2[arr2.length/2];
                }
                return temp;
    
            }else if(arr2==null||arr2.length==0){
                int temp=0;
                if((arr1.length&1)==0) //偶数 
                {
                   temp=arr1[arr1.length/2-1];
                }else{
                    temp=arr1[arr1.length/2];
                }
                return temp;
    
            }
            int mid=(arr1.length+arr2.length)/2; //要寻找的中位数
            // int low=0;
            // int arr1Mid=binaryFind(arr1,low,arr1.length-1);
            // int arr2Mid=binaryFind(arr2,low,arr2.length-1);;
            // System.out.println(arr1Mid);
            // System.out.println(arr2Mid);
            int re=0;
            int count=arr1.length+arr2.length;
            int[]arr=new int[count];
    
            for(int i=0;i<arr1.length;i++)
            {
              arr[i]=arr1[i];
              arr[arr.length-1-i]=arr2[i];
            }
            Arrays.sort(arr);
            return arr[arr.length/2-1];
        }
    
        //方法二(二分查找法)
        public static int getShangMidNum02(int[]arr1,int[]arr2)
        {
          if((arr1==null&&arr2==null)||(arr1.length==0&&arr2.length==0)){
                 throw new RuntimeException("Your arr is invalid!");
            }else if(arr1==null||arr1.length==0){
                int temp=0;
                if((arr2.length&1)==0) //偶数
                {
                    temp=arr2[arr2.length/2-1];
                }else{
                    temp=arr2[arr2.length/2];
                }
                return temp;
    
            }else if(arr2==null||arr2.length==0){
                int temp=0;
                if((arr1.length&1)==0) //偶数 
                {
                   temp=arr1[arr1.length/2-1];
                }else{
                    temp=arr1[arr1.length/2];
                }
                return temp;
    
            }
          int start1=0;
          int end1=arr1.length-1;
          int start2=0;
          int end2=arr2.length-1;
          int mid1=0;
          int mid2=0;
          int offset=0;
          while(start1<end1){
    
             mid1=(start1+end1)/2;
             mid2=(start2+end2)/2;
             //元素个数为奇数，offset=0;元素个数为偶数，则offset=1
             offset=((end1-start1+1)&1)^1;
             if(arr1[mid1]>arr2[mid2]){
                end1=mid1;
                start2=mid2+offset;
             }else if(arr1[mid1]<arr2[mid2]){
                start1=mid1+offset;
                end2=mid2;
             }else{
                return arr1[mid1];
             }
          }
          return Math.min(arr1[start1],arr2[start2]);
        }
        public  static void main(String[]args){
    
            //System.out.println("Hello");
            int[]arr1={
       1,2,3,4};
            int[]arr2={
       3,4,5,6};
            //int[]arr2={};
            System.out.println(getShangMidNum(arr1,arr2));
            System.out.println(getShangMidNum02(arr1,arr2));
            int[]arr3={
       0,1,2};
            int[]arr4={
       3,4,5};
            System.out.println(getShangMidNum(arr3,arr4));
            System.out.println(getShangMidNum02(arr3,arr4));
    
    
        }
    }

![这里写图片描述][70 1]

[70]: /images/20220526/fae52aaef22944f89ae1c54c45110f96.png
[70 1]: /images/20220526/89936777e8b749b1bc5f280c3b8f5613.png