LeetCode||寻找两个有序数组的中位数--给定两个大小为 m 和 n 的有序数组 nums1 和 nums2

向右看齐 2021-11-11 00:18 220阅读 0赞

## 题目描述： ##

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

## 实现代码： ##

public class 两个数组的中位数 {
    	public static double findMedianSortedArrays(int[] A, int[] B) {
    		int m = A.length;
    		int n = B.length;
    		int halfLen = (m + n + 1) / 2;
    		int min = 0;
    		int max = m;
    		
    		if (m > n) {
    			max = m;
    		}else {
    			max = n;
    		}
    		
    		while (min <= max) {
    			int a = (min + max) / 2;
    			int b = halfLen - a;
    			
    			if (a < max && B[b - 1] > A[a]) {
    				min = a + 1;
    				
    			} else if (a > min && A[a - 1] > B[b]) {
    				max = a - 1;
    				
    			} else {
    				
    				int maxL = 0;
    				if (a == 0) {
    					maxL = B[b - 1];
    				} else if (b == 0) {
    					maxL = A[a - 1];
    				} else {
    					maxL = Math.max(A[a - 1], B[b - 1]);
    				}
    				if ((m + n) % 2 == 1) {
    					return maxL;
    				}
    
    				int minR = 0;
    				if (a == m) {
    					minR = B[b];
    				} else if (b == n) {
    					minR = A[a];
    				} else {
    					minR = Math.min(B[b], A[a]);
    				}
    
    				return (maxL + minR) / 2.0;
    			}
    		}
    		return 0.0;
    	}
    
    	public static void main(String[] args) {
    		int[] A = { 1, 2, 4, 5 };
    		int[] B = { 3, 6, 8, 7 };
    		System.out.println("中位数为: "+findMedianSortedArrays(A,B));
    	}
    }

输出示例：

![20190803221825784.png][]

[20190803221825784.png]: /images/20211109/268d5231023243769294385cc92dab3c.png