欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

分治法求两个有序数组的中位数(LeedCode4)

程序员文章站 2022-06-03 16:59:39
...

分治法求两个有序数组的中位数

算法步骤(基本原理是获取第k小的数)
   	先取两个中间索引x_mid,y_mid;
    下面来比较
    如果x[x_mid]比较小,那么就看x_mid最大是第几小(记作m)
    ①m<k;
    则把x_mid及以前的全部删除,同时变换k的值
    同时如果也要把y_mid及右边的尽可能的删除
    ②如果m==k
    则把x_mid以前的全部删除并且保留x_mid
    同时如果也要把y_mid及右边的尽可能的删除
    同理如果y大也一样
    如此递归,最后到递归出口为k==1或者有数组为空了
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums2.length==0){
            if(nums1.length%2==0){
                return (double) (nums1[(nums1.length-1)/2]+nums1[(nums1.length-1)/2+1])/2.0;
            }else
                return (double)nums1[(nums1.length-1)/2];
        }else if(nums1.length==0){
            if(nums2.length%2==0){
                return (double) (nums2[(nums2.length-1)/2]+nums2[(nums2.length-1)/2+1])/2.0;
            }else
                return (double)nums2[(nums2.length-1)/2];
        }
        
        int i;
        if((nums1.length+nums2.length)%2==0){
            i=(nums1.length+nums2.length)/2;
            return (get_Middle_num(nums1,0,nums1.length-1,nums2,0,nums2.length-1,i)     
+get_Middle_num(nums1,0,nums1.length-1,nums2,0,nums2.length-1,i+1))/2.0;
        }
        else{
            i=(nums1.length+nums2.length)/2+1;
            return (double)get_Middle_num(nums1,0,nums1.length-1,nums2,0,nums2.length-1,i);
        }
    }
    int get_Middle_num(int x[],int left_x,int right_x,int y[],int left_y,int right_y,int k){*/
        if(left_x>right_x){
            return y[left_y+k-1];
        }else if(left_y>right_y){
            return x[left_x+k-1];
        }else if(k==1){
                return x[left_x]>y[left_y]?y[left_y]:x[left_x];
        }else{
            int x_mid = (left_x+right_x)/2;
            int y_mid = (left_y+right_y)/2;
            int num = (x_mid-left_x)+(y_mid-left_y);
            //注意num+1代表含义:x_mid可以到达的最大第几小
            // num+2代表含义:y_mid可以到达的最小第几小
            if(x[x_mid]<=y[y_mid]){
                //接下来我们开始锁定x左边界和y的右边界
                if(num+2==k){
                    right_y=y_mid;
                }else if(num+2>k)
                    right_y=y_mid-1;

                if(num+1<k){
                    k-=x_mid+1-left_x;
                    left_x=x_mid+1;
                }
                else if(num+1==k){
                    k-=x_mid-left_x;
                    left_x=x_mid;
                }
               return get_Middle_num(x,left_x, right_x,y,left_y,right_y,k);
            }else{
                 //接下来我们开始锁定x左边界和y的右边界
                if(num+2==k){
                    right_x=x_mid;
                }else if(num+2>k)
                    right_x=x_mid-1;

                if(num+1<k){
                    k-=y_mid+1-left_y;
                    left_y=y_mid+1;
                }
                else if(num+1==k){
                    k-=y_mid-left_y;
                    left_y=y_mid;
                }
               return get_Middle_num(x,left_x, right_x,y,left_y,right_y,k);
            }
        }
    }
}

算法复杂度分析:
T(n)=T(n/4)+O(1)
分治法求两个有序数组的中位数(LeedCode4)
O(n)=logn
分治法求两个有序数组的中位数(LeedCode4)
最后附上测试用例来供读者使用

    @Test
    public  void Test(){
        //[76,89,104,30823,31070,31259,31324,31714,31971,320331]
        //[122,2919,2941,17754,17781,17830,17874,18019,18023,18130]
        //[2634,2764,2801,30823,31070,31259,32319,32350,32408,32475,32681,32701,32764]
        //[122,32605,32641,32716,32757]
        int x[]={2634,2764,2801,30823,31070,31259,32319,32350,32408,32475,32681,32701,32764};
        int y[]={122,32605,32641,32716,32757};
        System.out.println(get_Middle_num(x,0,x.length-1,y,0,y.length-1,1));
        System.out.println((x.length+y.length));
    }
相关标签: # 分治法