LeetCode之寻找两个正序数组的中位数（四）

目录

题目

解题

方法一、C++

方法二、Java

题目

（原题链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/）

给定两个大小为 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

解题

方法一、C++

代码：

  

   

    

     

    
    

     

      #define max(a,b) (((a) > (b)) ? (a) : (b))
     
    
   

    

     

    
    

     

      #define min(a,b) (((a) < (b)) ? (a) : (b))
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

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

    

     

    
    

     
 int n = nums1.size();
     
    
   

    

     

    
    

     
		int m = nums2.size();
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
		if (n > m) {
     
    
   

    

     

    
    

     
			return findMedianSortedArrays(nums2, nums1);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
		int LMax1, LMax2, RMin1, RMin2, c1, c2, low = 0, high = 2 * n;
     
    
   

    

     

    
    

     
		while (low <= high) 
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			c1 = (low + high) / 2;  
     
    
   

    

     

    
    

     

      			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) {
     
    
   

    

     

    
    

     

       high = c1 - 1;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
			else if (LMax2 > RMin1) {
     
    
   

    

     

    
    

     

       low = c1 + 1;
     
    
   

    

     

    
    

     

       } else {
     
    
   

    

     

    
    

     
 break;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      };
     
    
  
 

执行结果：

方法二、Java

代码：

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
 public double findMedianSortedArrays(int[] nums1, int[] nums2) {
     
    
   

    

     

    
    

     
 int m = nums1.length;
     
    
   

    

     

    
    

     
 int n = nums2.length;
     
    
   

    

     

    
    

     
 int len = m + n;
     
    
   

    

     

    
    

     
 int left = -1, right = -1;
     
    
   

    

     

    
    

     
 int aStart = 0, bStart = 0;
     
    
   

    

     

    
    

     
 for (int i = 0; i <= len / 2; i++) {
     
    
   

    

     

    
    

     

       left = right;
     
    
   

    

     

    
    

     
 if (aStart < m && (bStart >= n || nums1[aStart] < nums2[bStart])) {
     
    
   

    

     

    
    

     

       right = nums1[aStart++];
     
    
   

    

     

    
    

     

       } else {
     
    
   

    

     

    
    

     

       right = nums2[bStart++];
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if ((len & 1) == 0) { // 判断奇偶
     
    
   

    

     

    
    

     
 return (left + right) / 2.0;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else {
     
    
   

    

     

    
    

     
 return right;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

执行结果：

文章来源: liuzhen.blog.csdn.net，作者：Data-Mining，版权归原作者所有，如需转载，请联系作者。

原文链接：liuzhen.blog.csdn.net/article/details/106680689