C++打开LeetCCode的大门---------004（数组）

这是她

                                                                                             寻找两个正序数组的中位数
题目：
给定两个大小为 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

代码：

#include <stdio.h>
#include <vector>

using namespace std;

#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
#define INT_MIN
#define INT_MAX

class Solution {
public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
                //动态数组的大小 
                int n = nums1.size();
                int m = nums2.size();

                //保证动态数组Array中第一个数组最短 
                if (n > m) 
                {
                        return findMedianSortedArrays(nums2, nums1);
                }
                
                //c1->第一个数组被分开的标记；LMax1->第一个数组被分开以后的左元素；LMin1->第一个数组被分开以后的右元素；
                //c2->第二个数组被分开的标记；LMax2->第二个数组被分开以后的左元素；LMin2->第二个数组被分开以后的右元素；
                int LMax1, LMax2, RMin1, RMin2, c1, c2, low = 0, hig = 2 * n;  //我们目前是虚拟加了'#'所以数组1是2*n长度

                while (low <= hig)   //二分
                {
                        c1 = (low + hig) / 2;  //c1是二分的结果
                        c2 = m + n - c1;//两个数组虚拟加了#，所以每个数组的个数是奇数个。2c1+1+2c2+1=2m+2n+2->c1+c2=m+n->c2=m+n-c1 

                        LMax1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
                        RMin1 = (c1 == 2 * n) ? 
                        INT_MAX : nums1[c1 / 2];
                        LMax2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
                        RMin2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2];

                        if (LMax1 > RMin2)
                                hig = c1 - 1;
                        else if (LMax2 > RMin1)
                                low = c1 + 1;
                        else
                                break;
                }
                return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0;
        }
};


int main(int argc, char *argv[])
{
        vector<int> nums1 = (2,3,5);
        vector<int> nums2 = {1,4,7,9};
        
        Solution solution;
        double ret = solution.findMedianSortedArrays(nums1, nums2);
        return 0;
}

https://leetcode-cn.com/problems ... u-de-zhong-wei-shu/


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

fendouxs

学习学习，谢谢