Leetcode 4. 寻找两个正序数组的中位数_letcode 寻找两个正序组的中位数

1、问题分析

题目链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/submissions/

具体思路是：
1、 根据两个数组的总长度计算是否是 奇数还是偶数，
2、然后和两个链表合并的思路类似

  代码我已经进行了详细的注释，理解应该没有问题，读者可以作为参考，如果看不懂(可以多看几遍)，欢迎留言哦！我看到会解答一下。

2、问题解决

  笔者以C++方式解决。

#include "iostream"

using namespace std;

#include "algorithm"
#include "vector"
#include "queue"
#include "set"
#include "map"
#include "string"
#include "stack"

class Solution {
public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
        // 你可以假设 nums1 和 nums2 不会同时为空。
        // 所以我们只需处理一种 nums 为空的情况
        if (nums1.empty()) {
            return dealOne(nums2);
        }
        // 所以我们只需处理一种 nums 为空的情况
        if (nums2.empty()) {
            return dealOne(nums1);
        }

        // 处理两个数组都不为空的情况
        return dealTwo(nums1, nums2);
    }

    /**
     * 寻找两个正序数组的中位数
     * 具体思路是：
     *          根据两个数组的总长度计算是否是 奇数还是偶数，
     *          然后和两个链表合并的思路类似
     * @param nums1
     * @param nums2
     * @return
     */
    double dealTwo(vector<int> &nums1, vector<int> &nums2) {

        // 计算总长度
        int all_length = nums1.size() + nums2.size();
        // 获取中位数索引
        int mid = all_length / 2;
        // 标记正在处理的节点索引
        int now = 0;
        // 初始化两个数组的开始处理节点
        int i = 0, j = 0;
        // 如果两个数组的总长度和为偶数，说明是两个数和的平均值
        if (all_length % 2 == 0) {
            // 保存前中位数
            int temp = 0;
            // 如果两个数组都没有递归到最后
            while (i < nums1.size() && j < nums2.size()) {
                // 找到了前中位数
                if (now == mid - 1) {
                    // 给前中位数赋值 为 nums1, nums2 数组中较小的一个
                    temp = nums1[i] <= nums2[j] ? nums1[i] : nums2[j];
                } else if (now == mid) {
                    // 后中位数  赋值 为 nums1, nums2 数组中较小的一个
                    // 两个中位数都取到了，直接返回结果
                    int temp2 = nums1[i] <= nums2[j] ? nums1[i] : nums2[j];
                    return (temp + temp2) * 1.0 / 2;
                }

                // 如果 nums1[i] 较小，则将其向右移动
                if (nums1[i] <= nums2[j]) {
                    i++;
                } else {
                    // 否则将nums2向右移动
                    j++;
                }
                // 当前处理的节点右移
                now++;
            }

            // 处理完一个数组，还有一个没有处理完
            while (i < nums1.size()) {
                // 找到了前中位数
                if (now == mid - 1) {
                    // 给前中位数赋值 为 nums1中的元素
                    temp = nums1[i];
                } else if (now == mid) {
                    // 后中位数  赋值 为 nums1中的元素
                    // 两个中位数都取到了，直接返回结果
                    int temp2 = nums1[i];
                    return (temp + temp2) * 1.0 / 2;
                }
                // 将 nums1 向右移动
                i++;
                // 当前处理的节点右移
                now++;
            }

            // 处理完一个数组，还有一个没有处理完
            // 思路和上面的类似
            while (j < nums2.size()) {
                // 找到了前中位数
                if (now == mid - 1) {
                    // 给前中位数赋值 为 nums2 中的元素
                    temp = nums2[j];
                } else if (now == mid) {
                    // 后中位数  赋值 为 nums2 中的元素
                    // 两个中位数都取到了，直接返回结果
                    int temp2 = nums2[j];
                    return (temp + temp2) * 1.0 / 2;
                }
                // 将 nums2 向右移动
                j++;
                // 当前处理的节点右移
                now++;
            }
        } else {
            // 如果两个数组的总长度和为奇数，说明是一个值
            while (i < nums1.size() && j < nums2.size()) {
                // 找到中位数 取值 nums1, nums2 数组中较小的一个，直接返回
                if (now == mid) {
                    return nums1[i] <= nums2[j] ? nums1[i] : nums2[j];
                }

                // 如果 nums1[i] 较小，则将其向右移动
                if (nums1[i] <= nums2[j]) {
                    i++;
                } else {
                    // 否则将nums2向右移动
                    j++;
                }
                // 当前处理的节点右移
                now++;
            }

            // 处理完一个数组，还有一个没有处理完
            while (i < nums1.size()) {
                // 找到中位数 直接返回
                if (now == mid) {
                    return nums1[i];
                }
                // 将 nums1 向右移动
                i++;
                // 当前处理的节点右移
                now++;
            }

            // 处理完一个数组，还有一个没有处理完
            // 思路和上面类似
            while (j < nums2.size()) {
                // 找到中位数 直接返回
                if (now == mid) {
                    return nums2[j];
                }
                // 将 nums2 向右移动
                j++;
                // 当前处理的节点右移
                now++;
            }
        }

        // 防止编译错误
        return -1.0;

    }

    /**
     * 具体思路是：
     *          根据数组的长度，分为两种情况：
     *          1、如果是奇数，则直接选取中间节点
     *          2、如果是偶数，则选择中间两个节点，求和并返回平均值
     * @param nums
     * @return
     */
    double dealOne(vector<int> &nums) {
        // 计算数组长度
        int size_chen = nums.size();
        // 获取中位数 索引
        int mid = size_chen / 2;
        // 分奇偶数两种情况，如果是偶数
        if (size_chen % 2 == 0) {
            // 则选择中间两个节点，求和并返回平均值，注意这里要  * 1.0 ，否则 int 类型
            // 处理之后还是 int 类型，会出现精度丢失
            return (nums[mid] + nums[mid - 1]) * 1.0 / 2;
        } else {
            // 如果是奇数，则直接选取中间节点
            return nums[mid];
        }
    }
};

int main() {
    vector<int> nums1 = {1, 2};
    vector<int> nums2 = {3, 4};

    Solution *pSolution = new Solution;
    double d = pSolution->findMedianSortedArrays(nums1, nums2);
    cout << d << endl;
    system("pause");
    return 0;
}
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197

运行结果

有点菜，有时间再优化一下。

3、总结

  难得有时间刷一波LeetCode, 这次做一个系统的记录，等以后复习的时候可以有章可循，同时也期待各位读者给出的建议。算法真的是一个照妖镜，原来感觉自己也还行吧，但是算法分分钟教你做人。前人栽树，后人乘凉。在学习算法的过程中，看了前辈的成果，受益匪浅。
感谢各位前辈的辛勤付出，让我们少走了很多的弯路！
哪怕只有一个人从我的博客受益，我也知足了。
点个赞再走呗！欢迎留言哦！