【水滴计划】：合并两个有序数组、寻找两个正序数组的中位数

1、写在前面

大家好，我是翼同学，这里是【水滴计划 | 刷题日志】

每日两题，拒绝摆烂。

2、内容

2.1、题目一：合并两个有序数组

链接：88. 合并两个有序数组 - 力扣（LeetCode）

(1) 描述

(2) 举例

(3) 解题

解法一：将数组2中的元素替换掉数组1中的零元素，再进行排序。

代码如下：

class Solution {
public:
    void merge(vector& nums1, int m, vector& nums2, int n) {
        for(int i = 0; i < n; i++) {
            nums1[m++] = nums2[i];
        }
        sort(nums1.begin(), nums1.end());
    }
};
1
2
3
4
5
6
7
8
9

解法二：是利用两个数组的自身条件，即非递减有序数组，对比两个数组的末尾元素，谁大就放在数组1的末尾，以此类推。

代码如下：

class Solution {
public:
    void merge(vector& nums1, int m, vector& nums2, int n) {
        int pos = nums1.size() - 1;
        m--;
        n--;
        while(m >= 0 && n >= 0) {
            if(nums1[m] > nums2[n]) {
                nums1[pos--] = nums1[m--];
            }else {
                nums1[pos--] = nums2[n--];
            }
        }
        while(n >= 0) {
            nums1[pos--] = nums2[n--];
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.2、题目二：寻找两个正序数组的中位数

链接：4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

(1) 描述

(2) 举例

(3) 解题

第一种思路是直接合并两个数组，再寻找中位数。

代码如下：

class Solution {
public:
    double findMedianSortedArrays(vector& nums1, vector& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int* nums = new int[m+n];
        // 1. 处理 m 等于 0 的情况
        if (m == 0) {
            if (n % 2 == 0) {
                return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
            } else {
                return nums2[n / 2];
            }
        }
        // 2. 处理 n 等于 0 的情况
        if (n == 0) {
            if (m % 2 == 0) {
                return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
            } else {
                return nums1[m / 2];
            }
        }
        int count = 0;
        int i = 0, j = 0;
        // 3. 合并两个有序数组到数组 nums
        while (count != (m+n)) {
            // 3.1 当 i 等于 数组1 的长度m时进入if语句块
            if (i == m) {
                while (j != n) {
                    nums[count++] = nums2[j++];
                }
                break;
            }
            // 3.2 当 j 等于 数组2 的长度n时进入if语句块
            if (j == n) {
                while (i != m) {
                    nums[count++] = nums1[i++];
                }
                break;
            }
            // 3.3 哪个元素小就放到数组nums中
            if (nums1[i] < nums2[j]) {
                nums[count++] = nums1[i++];
            } else {
                nums[count++] = nums2[j++];
            }
        }
        // 4. 寻找中位数（数组长度如果是奇数则刚好中间的数就是答案，偶数则需要相加中间两个数后除以2）
        if (count % 2 == 0) {
            return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
        } else {
            return nums[count / 2];
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

---

另一种思路就是，不用合并数组，利用数组有序的特点，在两个数组中找到中位数的位置。那么这里该如何寻找中位数的位置？

1. 首先是循环次数的确定，用len表示合并后数组的长度（并不是真的合并），那么循环条件就是i <= len/2；
2. 这里我们定义a1指向了当前数组1的索引，定义a2指向当前数组2的索引。
3. 然后，用right保存当前循环的结果，用left保存上一次循环的值；
4. 这样定义后，如果合并后的数组长度是奇数，则中位数则取right的值，如果是偶数，则用(left + right)/2.0的方法来得到中位数。
5. 重点来了，在每次循环下，该怎么设置right的值？
6. 是这样的，如果a1的值小于数组1的长度m并且此时数组1的值nums1[a1]小于数组2的值nums2[a2]，就将right赋值为nums1[a1]，并且a1自增加一，否则就赋值为nums2[a2]，并更新a2的值。
7. 但需要注意，如果满足a2 >= n的情况下再取值的话数组2就会越界;
8. 因此应该利用||短路表达式的技巧，丰富判断语句，即判断a2是否大于数组2的长度，如果大于就不用看后面nums1[a1] < nums2[a2])条件，而是直接将right赋值为nums1[a1].
9. 因此判断语句就是: if (a1 < m && (a2 >= n || nums1[a1] < nums2[a2]))

整体代码如下：

class Solution {
public:
    double findMedianSortedArrays(vector& nums1, vector& nums2) {
        int m = nums1.size();  // m为数组1的长度
        int n = nums2.size();  // n为数组2的长度
        int len = m + n;       // len表示数组合并后的长度
        int left = -1, right = -1;  // right表示中位数的位置，left用于计算奇数情况下的中位数
        int a1 = 0, a2 = 0;         // a1指向了当前数组1的索引值，a2指向当前数组2的索引值。
        // 循环遍历次数为len/2, 寻找中位数right
        for (int i = 0; i <= len / 2; i++) {
            left = right;  // left保存上一次循环时的结果
            if (a1 < m && (a2 >= n || nums1[a1] < nums2[a2])) {
                right = nums1[a1];
                a1++;
            } else {
                right = nums2[a2];
                a2++;
            }
        }
        // 计算中位数
        if (len % 2 == 0)
            return (left + right) / 2.0;
        else
            return right;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

---

3、写在最后

好了，今天就刷到这里，明天再来。