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

这是她

                                                                                             寻找两个正序数组的中位数
题目：
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例1：

1. nums1 = [1, 3]
   
2. nums2 = [2]
   
3. 
   
4. 则中位数是 2.0

复制代码

示例2：

1. nums1 = [1, 2]
   
2. nums2 = [3, 4]
   
3. 
   
4. 则中位数是 (2 + 3)/2 = 2.5

复制代码

代码：

1. #include <stdio.h>
   
2. #include <vector>
   
3. 
   
4. using namespace std;
   
5. 
   
6. #define max(a,b) (((a) > (b)) ? (a) : (b))
   
7. #define min(a,b) (((a) < (b)) ? (a) : (b))
   
8. #define INT_MIN
   
9. #define INT_MAX
   
10. 
    
11. class Solution {
    
12. public:
    
13.         double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    
14.                 //动态数组的大小
    
15.                 int n = nums1.size();
    
16.                 int m = nums2.size();
    
17. 
    
18.                 //保证动态数组Array中第一个数组最短
    
19.                 if (n > m)
    
20.                 {
    
21.                         return findMedianSortedArrays(nums2, nums1);
    
22.                 }
    
23.                
    
24.                 //c1->第一个数组被分开的标记；LMax1->第一个数组被分开以后的左元素；LMin1->第一个数组被分开以后的右元素；
    
25.                 //c2->第二个数组被分开的标记；LMax2->第二个数组被分开以后的左元素；LMin2->第二个数组被分开以后的右元素；
    
26.                 int LMax1, LMax2, RMin1, RMin2, c1, c2, low = 0, hig = 2 * n;  //我们目前是虚拟加了'#'所以数组1是2*n长度
    
27. 
    
28.                 while (low <= hig)   //二分
    
29.                 {
    
30.                         c1 = (low + hig) / 2;  //c1是二分的结果
    
31.                         c2 = m + n - c1;//两个数组虚拟加了#，所以每个数组的个数是奇数个。2c1+1+2c2+1=2m+2n+2->c1+c2=m+n->c2=m+n-c1
    
32. 
    
33.                         LMax1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
    
34.                         RMin1 = (c1 == 2 * n) ?
    
35.                         INT_MAX : nums1[c1 / 2];
    
36.                         LMax2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
    
37.                         RMin2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2];
    
38. 
    
39.                         if (LMax1 > RMin2)
    
40.                                 hig = c1 - 1;
    
41.                         else if (LMax2 > RMin1)
    
42.                                 low = c1 + 1;
    
43.                         else
    
44.                                 break;
    
45.                 }
    
46.                 return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0;
    
47.         }
    
48. };
    
49. 
    
50. 
    
51. int main(int argc, char *argv[])
    
52. {
    
53.         vector<int> nums1 = (2,3,5);
    
54.         vector<int> nums2 = {1,4,7,9};
    
55.        
    
56.         Solution solution;
    
57.         double ret = solution.findMedianSortedArrays(nums1, nums2);
    
58.         return 0;
    
59. }

复制代码

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


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

fendouxs

学习学习，谢谢