LeetCode - Median of Two Sorted Arrays

写在前面

新年好!

开年第一题, 祝龙年行大运!

思路1: 数组合并, 找到中间元素

合并后的数组长度为奇数, 存在中间元素; 为偶数, 取中间两元素的平均值

输入数组长度可以为0, 但不会都为0

解答

Copy 1class Solution {
 2public:
 3    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
 4        auto cnt1 = nums1.size(), cnt2 = nums2.size(), avg = (cnt1 + cnt2) / 2;
 5        auto i = 0, j = 0;
 6        double last = -1.0, cur = -1.0;
 7        while (i + j <= avg)
 8        {
 9            last = cur;
10            if (i == cnt1)
11            {
12                cur = nums2[j];
13                ++j;
14            }
15            else if (j == cnt2)
16            {
17                cur = nums1[i];
18                ++i;
19            }
20            else 
21            {
22                if (nums1[i] < nums2[j])
23                {
24                    cur = nums1[i];
25                    ++i;
26                }
27                else
28                {
29                    cur = nums2[j];
30                    ++j;
31                }
32            }
33        }
34
35        if (avg * 2 < cnt1 + cnt2)
36        {
37            return cur;
38        }
39        else
40        {
41            return (cur + last) / 2;
42        }
43    }
44};

思路2: 数组有序, 二分确定边界

数组本身是有序的

思路1中的挨个遍历, 有两个用处:

• 确定前半段的元素
  
• 确定中间元素
  

确定前半段元素时, 采用二分法更高效

处理中间元素

1. 拿奇数举例: 两个数组大小之和为3
   

   • 需要索引为1的元素
     

     3 / 2 = 1

     (3 - 1) / 2 = 1

2. 拿偶数举例: 两个数组大小之和为4
   

   • 需要索引为1和2的元素
     

     4 / 2 = 2

     (4 - 1) / 2 = 1

若元素个数为n, 需求索引为 n / 2 的元素和索引为 (n - 1) / 2 的元素, 取二者平均值

二分法

确定前半段元素

• 假定前半段元素个数为 (n1 + n2) / 2 , 这些元素分别来自两个数组
  
• 假设数组1中取 x 个元素, 数组2中取 y 个元素
  

  x + y = (n1 + n2) / 2

• 使得数组1中的元素个数不大于数组2, 那么前半段的元素个数不会小于数组1的大小
  
• 初始情形: 在数组1全体元素中使用二分查找确定边界; 剩余元素来自数组2
  

判断元素组合是否满足条件

数组1, 长度 n1 = 5

1 3 5 7 9

数组2, 长度 n2 = 7

2 4 6 8 10 12 14

此时, 前半段元素个数为:

(n1 + n2) / 2 = 6

• 数组1中选取元素的边界

  x = (beg + end) / 2 = 2 : beg 初始为0, end 初始为数组大小
  

  INDEX           0            1 2     3 4
  ELEMENT         1            3 5     7 9 -
  SAVED INDEX     beg            x         end

• 数组2中选取元素的边界

  y = 6 - x = 4
  

  INDEX            0 1 2 3 4  5  6
  ELEMENT          2 4 6 8 10 12 14
  SAVED INDEX              y

• 终止条件

  • x 和 y 的左侧共有6个元素, 满足当前总共偶数个元素的一半
    
  • 需要判断这6个元素是否为所有元素从小到大排序的前6个
    

  使用 max1 保存数组1中选取元素的最大值, max2 保存数组2中选取元素的最大值; 使用 cur1 保存数组1边界元素的值, 使用 cur2 保存数组2边界元素的值
  

  INDEX           0            1        2     3 4
  ELEMENT         1            3        5     7 9 -
  SAVED INDEX     beg          x - 1    x         end
  SAVED ELEMENT                max1     cur1
  
  INDEX             0 1 2 3       4     5  6
  ELEMENT           2 4 6 8       10    12 14
  SAVED INDEX             y - 1   y
  SAVED ELEMENT           max2    cur2  

  如果 max1 不大于 cur2 , 且 max2 不大于 cur1 , 可以确定这6个元素均不大于 cur1 和 cur2
  

  这6个元素再加上 cur1 和 cur2 中的较小值, 则构成的所有元素的前半段
  

  • 奇数个元素

    返回 cur1 和 cur2 的较小者作为中间元素
    

  • 偶数个元素

    将 max1 和 max2 中的较大者与 cur1 和 cur2 中的较小者取平均值之后返回
    

• 移动数组1中的边界

  INDEX           0            1        2     3 4
  ELEMENT         1            3        5     7 9 -
  SAVED INDEX     beg          x - 1    x         end
  SAVED ELEMENT                max1     cur1
  
  INDEX             0 1 2 3       4     5  6
  ELEMENT           2 4 6 8       10    12 14
  SAVED INDEX             y - 1   y
  SAVED ELEMENT           max2    cur2  

  当前数组1中的边界无法涵盖数组2中选取的元素, 需要将 x 右移, 这会导致 y 左移
  

  Copy1if (max2 > cur1)
  2{
  3    beg = x + 1;
  4}

考虑索引的有效性

x 可能取到尾后元素, 而 x - 1 可以为首前元素

使用 int 类型宏 INT_MIN 和 INT_MAX 作为越界的元素值

解答

Copy 1class Solution {
 2public:
 3    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
 4        int n1 = nums1.size(), n2 = nums2.size();
 5        if (n1 > n2)
 6        {
 7            return findMedianSortedArrays(nums2, nums1);
 8        }
 9
10        int avg = (n1 + n2) / 2;
11        int beg = 0, end = n1;
12
13        while (beg <= end)
14        {
15            int x = (beg + end) >> 1;
16            int y = avg - x;
17
18            int max1 = INT_MIN, max2 = INT_MIN, cur1 = INT_MAX, cur2 = INT_MAX;
19
20            if (x < n1)
21            {
22                cur1 = nums1[x];
23            }
24            if (x - 1 >= 0)
25            {
26                max1 = nums1[x - 1];
27            }
28            if (y < n2)
29            {
30                cur2 = nums2[y];
31            }
32            if (y - 1 >= 0)
33            {
34                max2 = nums2[y - 1];
35            }
36
37            if (max1 <= cur2 && max2 <= cur1)
38            {
39                if ((n1 + n2) % 2 == 0)
40                {
41                    return ((double)(min(cur1, cur2) + max(max1, max2))) / 2.0;
42                }
43                else
44                {
45                    return min(cur1, cur2);
46                }
47            }
48            else
49            {
50                if (max1 > cur2)
51                {
52                    end = x - 1;
53                }
54                else
55                {
56                    beg = x + 1;
57                }
58            }
59        }
60
61        return 0;
62    }
63};