leetcode題解Java | 4. Median of Two Sorted Arrays

題目：https://leetcode.com/problems/median-of-two-sorted-arrays/#/description

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
      

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5      

分析 ：

這道題的難點在于實作如何才能簡潔。這是個二次二分的題，開始我隻想到在nums1中二分，找到數nums1[mid1]後，找在nums2中的位置，再判斷是否找到。這樣，就需要在nums1和nums2上同時二分，再加上越界的判斷問題，實作起來就比較困難。

後來看了stellari 的solution，确實是很巧妙的方法，用特殊的方法表示了分隔符，把奇偶的情況合二為一，且巧妙地處理了數組越界。下面簡述一個他的方法，如有什麼不清楚的，請看原文連結

首先，可以把奇數和偶數的情況合二為一，如 [2 3 4 5 6]，我們可以這樣分隔[2 3 (4/4) 5 7]

設斜杠左右的索引為L，R，那麼 L = (N-1)/2, R = N/2

A[mid] = (A[(N-1)/2] + A[N/2])/2

現在為了表示斜杠，我們在數字間插入#

A1: [# 1 # 2 # 3 # 4 # 5 #]    (N1 = 5, N1_positions = 11)

A2: [# 1 # 1 # 1 # 1 #]     (N2 = 4, N2_positions = 9)

可以推出index(L) = (CutPosition-1)/2, index(R) = (CutPosition)/2

如果A2的插入位是C2，那麼C1 = N1 + N2 - k，是以隻需要二分一個，另一個就能求到，時間複雜度為O（log(min(n1,n2)）

L1 = A1[(C1-1)/2]; R1 = A1[C1/2];

L2 = A2[(C2-1)/2]; R2 = A2[C2/2];

L1為A1插入符左邊的數，R1為A1插入符後邊的數

并且它們需要滿足

L1 <= R1 && L1 <= R2&& L2 <= R1 && L2 <= R2

Java實作：

public double findMedianSortedArrays(int[] nums1, int[] nums2)
	{
		int n1 = nums1.length;
		int n2 = nums2.length;
		if(n2>n1) return findMedianSortedArrays(nums2, nums1);
		if(n2==0) return (nums1[(n1-1)/2]+nums1[n1/2])/2.0;
		int lo=0, hi=n2*2;
		while(lo<=hi)
		{
			int mid2 = (lo+hi)/2;
			int mid1 = n1+n2-mid2;
			int l1 = (mid1==0)? Integer.MIN_VALUE: nums1[(mid1-1)/2];//處理數組越界的情況
			int r1 = (mid1==2*n1)? Integer.MAX_VALUE: nums1[mid1/2];
			int l2 = (mid2==0)? Integer.MIN_VALUE: nums2[(mid2-1)/2];
			int r2 = (mid2==2*n2)? Integer.MAX_VALUE: nums2[mid2/2];
			if(l1>r2)
				lo = mid2+1;
			else if(l2>r1)
				hi = mid2-1;
			else
				return ((double)Integer.max(l1, l2)+(double)Integer.min(r1, r2))/2;
		}
		return -1;
	}