[leetcode]分治算法之Median of Two Sorted Arrays

灰太狼 2021-09-28 14:00 258阅读 0赞

### 分治算法之Median of Two Sorted Arrays ###

*  题干
 *  思想归类
 *  代码

# 题干 #

[leetcode入口][leetcode]

# 思想归类 #

中位数的计算：  
假设第一个集合大小为size1，第二个为size2,  
那么中位数可以是第 `(size1+size2+1)/2` 和 `(size1+size2+2)/2` 这两个位置的值  
利用分治法，求这两个位置的值。

二分法：  
求两个有序数组中第K小的数组，对K进行二分  
查找到nums1和nums2中第K/2大的数，淘汰掉较小的一个数组的K/2个数组(通过移动下标来实现)  
如果数组大小小于K/2，那么淘汰掉另一个数组的K/2个数

# 代码 #

class Solution { 
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 
            int size1=nums1.size();
            int size2=nums2.size();
            
            //如果nums1和nums2的总数是奇数，那么下面这两个相等，否则不相等
            int left = (size1+size2+1)/2; //左边的数位置
            int right= (size1+size2+2)/2; //右边的数位置
            
            //此题变成了寻找两个有序数组中第K大的问题
            return ((double)divide_and_conquer(nums1,0,nums2,0,left)+divide_and_conquer(nums1,0,nums2,0,right))/2.0;
            
        }
        
        //i代表nums1的起始位置,j代表nums2的起始位置
        int divide_and_conquer(vector<int>& nums1,int i,vector<int>& nums2,int j,int K){ 
            //如果起始位置超过各个数组的大小，则在另一个数组中找
            if(i>=nums1.size()) return nums2[j+K-1];
            if(j>=nums2.size()) return nums1[i+K-1];
            if (K == 1) return min(nums1[i], nums2[j]);
    		
    		//分别找到第K/2个数字进行比较
            int mid1=((i+K/2-1)<nums1.size())?nums1[i+K/2-1]:INT_MAX;
            int mid2=((j+K/2-1)<nums2.size())?nums2[j+K/2-1]:INT_MAX;
            
            //如果淘汰较小数组的前K/2个
            if(mid1<mid2){ 
                return divide_and_conquer(nums1,i+K/2,nums2,j,K-K/2);
            }
            else{ 
                return divide_and_conquer(nums1,i,nums2,j+K/2,K-K/2);
            }
            
            
        }
        
    };

[leetcode]: https://leetcode.com/problems/median-of-two-sorted-arrays/submissions/