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

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

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

• 1、问题分析
• 2、问题解决
• 3、总结

1、问题分析

题目链接：/

具体思路是：
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 (pty()) {return dealOne(nums2);}// 所以我们只需处理一种 nums 为空的情况if (pty()) {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;
}

运行结果

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

3、总结

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