Leetcode 4 Median of Two Sorted Arrays 二分查找（二分答案+二分下标）

貌似是去年阿里巴巴c++的笔试题，没有什么创新直接照搬的。。。

题意就是找出两个排序数组的中间数，其实就是找出两个排序数组的第k个数。

二分答案，先二分出一个数，再用二分算出这个数在两个排序数组排序第几，然后和k做比较，最后以这个比较为依据接着二分直到求出第k个数。

本来这是两重二分，由于楼主的懒已经没有办法治疗了，用库函数upper_bound()代替了第二重二分，有志者可以自己写第二重二分，楼主就偷懒了。。。

警告：由于题目很神奇，会出现两个排序数组为空的情况，楼主差点因为这个报警。。。。

 class Solution {

 public:

     int findkth(vector<int>& nums1, vector<int>& nums2, int k){

         int l = min(nums1[],nums2[]);

         int r = max(nums1[nums1.size() - ], nums2[nums2.size() - ]);

         while(l <= r){

             int mid = l + (r - l)/ ;

             int k1 = upper_bound(nums1.begin(), nums1.end(), mid) -  nums1.begin() ;

             int k2 = upper_bound(nums2.begin(), nums2.end(), mid) -  nums2.begin() ;

             if(k1 + k2 == k){

                 if(k1 >  && mid == nums1[k1 - ]) return mid;

                 else if(k2 >  && mid == nums1[k2 - ]) return mid;

                 else r = mid - ;

             }

             else if(k1 + k2 > k){

                 r = mid - ;

             }

             else l = mid + ;

         }

         return l;

     }

     double getmid(vector<int>& nums){

         if(nums.size() %  == ) return (nums[nums.size() /  - ] + nums[nums.size() / ]) / 2.0;

         else return nums[nums.size() / ];

     }

     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

         if(nums1.size() ==  && nums2.size() == ) return 0.0;

         if(nums1.size() == ) return getmid(nums2);

         if(nums2.size() == ) return getmid(nums1);

         int k = (nums1.size() + nums2.size() + ) / ;

         if((nums1.size() + nums2.size()) %  == ){

             return (findkth(nums1, nums2, k) + findkth(nums1, nums2, k + ))/2.0;

         }

         else return findkth(nums1, nums2, k);

     }

 };

巴特西

Leetcode 4 Median of Two Sorted Arrays 二分查找（二分答案+二分下标）

最新文章

热门文章