首页 > 代码库 > 4. Median of Two Sorted Arrays

4. Median of Two Sorted Arrays

2024-08-23 09:36:21   213人阅读

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
来源： https://leetcode.com/problems/median-of-two-sorted-arrays/

分析 原文链接

该问题难在于，我们首先会考虑到对奇偶序列分开讨论，但实际上，这两种情况是可以合并的。

偶数序列中位数计算是这样的：
  1. [2 3 5 7]
  2. 则
  3. [2 3 / 5 7]

奇数序列中位数是这样的：
  1. [2 3 4 5 6 7]
  2. 则
  3. [2 3 (4/4) 5 6 7]

使用 L 代表左边序列的最大值，R 代表右边序列的最小值，则中位数就是 (L+R)/2

下面观察 L 和 R 随着 序列长度N的变化，产生的规律
  1. N           Index of L / R
  2. 1               0 / 0
  3. 2               0 / 1
  4. 3               1 / 1  
  5. 4               1 / 2      
  6. 5               2 / 2
  7. 6               2 / 3
  8. 7               3 / 3
  9. 8               3 / 4
不难看出，L = ( N -1 ) / 2，R = N / 2。
所以中位数是：
  1. (L + R)/2 = (A[(N-1)/2] + A[N/2])/2

下面，为了对两个序列的中位数问题求解，首先我们对序列进行一下预处理。
想象每个数字中间，都有一个 ‘#’ ，则序列的表示如下：
  1. [6 9 13 18]  ->   [# 6 # 9 # 13 # 18 #]    (N = 4) 偶数序列
  2. position index     0 1 2 3 4 5  6 7  8     (N_Position = 9)
  3. 		  
  4. [6 9 11 13 18]->   [# 6 # 9 # 11 # 13 # 18 #]   (N = 5) 奇数序列
  5. position index      0 1 2 3 4 5  6 7  8 9 10    (N_Position = 11)
可以看到，无论原来的序列是奇数还是偶数，经过处理的序列，总是 2N+1，是一个奇数序列。所以 分割线 ‘/‘ 位置总是在第N个（处理后的序列，以0为起始）。从而：
  1. index ( L ) = ( N -1 ) / 2 = ( CutPosition - 1 ) / 2
  2. index ( R ) = N / 2 = CutPosition / 2; 
  3. //CutPosition: 处理后序列的分割线位置

下面来看两组序列中位数的情况：
  1. A1: [# 1 # 2 # 3 # 4 # 5 #]    (N1 = 5, N1_positions = 11)
  2. A2: [# 1 # 1 # 1 # 1 #]        (N2 = 4, N2_positions = 9)
和单序列求中位数情况类似，我们需要分割两个序列，使得其各自两部分，满足如下条件：
  1. 任意在 左半部分的数字 < 任意在 右半部分的数字
同时我们也可以做出如下推论：
1. A1 和 A2 两个序列总长度是 2*N1 + 2*N2 + 2。因此，分割以后，必须正好满足分割线左边部分位置个数为 N1 + N2，分割线右边位置个数也是 N1 + N2。两个分割线 ‘/‘ 占用 2 个位置。
2. 如果序列A2的分割线位置是C2 = k，那么A1的分割线位置C1应该满足 C1 = N1+N2 - k
3. 分割以后，会得到两个左半部分，两个右半部分，有如下关系：
  1.  L1 = A1[(C1-1)/2]; R1 = A1[C1/2];
  2.  L2 = A2[(C2-1)/2]; R2 = A2[C2/2];

接下来就需要决定怎样确定分割线 ‘/’ 的位置了。 L1, L2 是左半边最大的数字，R1，R2是右半边最小的数字，我们必须保证
  1. L1 <= R1 && L1 <= R2 && L2 <= R1 && L2 <= R2
因为L1 <= R1 和 L2 <= R2 是排序后数列自己保证的，所以我们简化条件为：
  1. L1 <= R2 && L2 <= R1
接下来我们就可以通过简单的 二分查找 binary search 找到结果了。
  1. 1. 如果有L1 > R2，则说明A1序列左半边有太多过大的数字，所以 我们需要将C1左移（或者C2右移）
  2. 2. 如果 L2 > R1，则说明A2序列左边有太多过大的数字，所以应该将C2左移（或者C1右移）
  3. 3. 如果都没有，那么说明该 分割线位置是正确的
  4. 4. 中位数medium就是 (max(L1,L2) + min(R1,R2)) / 2;
有两点需要注意：
  1. 1. C1和C2可以互相决定，所以我们可以选择短一些的序列进行查找，从而使得算法时间复杂度为log（min(N1,N2)）
  2. 2. 唯一的边界条件edge case是当分割线落在 0 和 2N 的位置上。比如：如果C2 = 2*N2，那么R2 = A2[ 2*N2 / 2] = A2[ N2 ]，会越过边界。为了解决这个问题，我们可以这样处理：当 L 落到左边界，则令 L = INT_MIN, 当 R落到 右边界，则让R = INT_MAX

下面就是代码：
  1.  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  2.     int N1 = nums1.size();
  3.     int N2 = nums2.size();
  4.     // Make sure A2 is the shorter one.
  5.     if (N1 < N2) return findMedianSortedArrays(nums2, nums1);	
  6.     // If A2 is empty
  7.     if (N2 == 0) return ((double)nums1[(N1-1)/2] + (double)nums1[N1/2])/2;      
  8.     int lo = 0, hi = N2 * 2;
  9.     while (lo <= hi) {
  10.         int mid2 = (lo + hi) / 2;   // Try Cut 2 
  11.         int mid1 = N1 + N2 - mid2;  // Calculate Cut 1 accordingly        
  12.         double L1 = (mid1 == 0) ? INT_MIN : nums1[(mid1-1)/2];	// Get L1, R1, L2, R2 respectively
  13.         double L2 = (mid2 == 0) ? INT_MIN : nums2[(mid2-1)/2];
  14.         double R1 = (mid1 == N1 * 2) ? INT_MAX : nums1[(mid1)/2];
  15.         double R2 = (mid2 == N2 * 2) ? INT_MAX : nums2[(mid2)/2];        
  16.         if (L1 > R2) lo = mid2 + 1;		// A1‘s lower half is too big; need to move C1 left (C2 right)
  17.         else if (L2 > R1) hi = mid2 - 1;	// A2‘s lower half too big; need to move C2 left.
  18.         else return (max(L1,L2) + min(R1, R2)) / 2;	// Otherwise, that‘s the right cut.
  19.     }
  20.     return -1;
  21. }







来自为知笔记(Wiz)


4. Median of Two Sorted Arrays


联系
我们