Go语言视频零基础入门到精通

admin

  
   
    4. 两个排序数组的中位数
   
  


  
   题目描述
   提示帮助
   提交记录
   社区讨论
   阅读解答
   
  
  
   
   
     
      随机一题
      

---

     
     
      
      
      
        
      
      
      
       给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
       请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
       示例 1:
      

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

复制代码

       示例 2:
      

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

复制代码

      
     
   
   
  

1. int compare(int* nums1,int* nums2,int i,int j){
2.     if(nums1[i] >= nums2[j])
3.         return 1;
4.     return 0;
5. }
6. double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
7.     double ans = 0;
8.     int p = 0,q = 0;
9.     int flag = (nums1Size + nums2Size + 1)/2;
10.     int flag1 = ((nums1Size + nums2Size) % 2 == 0) ? 2 : 1;
11.     int num = flag1;
12.     int count = 0;
13.    
14.     while(count < flag + 1){
15.         int temp = 0;
16.         if(p < nums1Size && q < nums2Size){
17.             if(compare(nums1,nums2,p,q) == 1)
18.                 temp = nums2[q++];
19.             else
20.                 temp = nums1[p++];
21.         }
22.         else if(p < nums1Size)
23.             temp = nums1[p++];
24.         else if(q < nums2Size)
25.             temp = nums2[q++];
26.         count++;
27.         if(flag <= count && flag1 > 0){
28.             flag1--;
29.             ans += temp;
30.         }
31.     }
32.     return (ans/num);
33. }

复制代码

这题的主要解题思路是通过双指针的方法进行的，首先通过判断该中位数为一个数还是两个数的平均值flag1 = ((nums1Size + nums2Size) % 2 == 0) ? 2 : 1;然后通过计数的方法依此的移动指针，直到移到中位数的位置然后获取值。时间复杂度为O(n + m)如果要进一步减小时间复杂度，可以考虑用二分查找的方法。