Leecode热题100---二分查找--4：寻找两个正序数组的中位数

本文主要是介绍Leecode热题100---二分查找--4：寻找两个正序数组的中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

在这里插入图片描述
解法1、暴力解法（归并）
思路：
合并 nums1，nums2 为第三个数组
排序第三个数组
按下标，找出中位数

class Solution
{
public:double findMedianSortedArrays(vector<int>& nums1,vector<int>& nums2){int m = nums1.size(), n = nums2.size(), k=0, i=0, j=0;vector<int> result(m+n,0);while(i<m && j<n){if(nums1[i] < nums2[j]){result[k] = nums1[i];i++;}else{result[k] = nums2[j];j++;}k++;}// nums1或nums2有一个已经遍历完while(i<m){result[k] = nums1[i];i++;k++;}while(j<n){result[k] = nums2[j];j++;k++;}// %:取余，判断奇偶return k % 2 ? result[k/2]:(result[k/2]+result[k/2-1])/2.0;}
};

解法2、双指针法
思路：
申请2个指针，分别指向2个数组的头
每次比较大小来移动 2个指针
当指针移动的次数与(m + n) / 2 相同时，得到中位数

注意边界问题：
2个指针在移动时，是否有超过2个数组的最大个数；
如果有，后续就只能移动另一个指针

class Solution
{
public:double findMedianSortedArrays(vector<int>& nums1,vector<int>& nums2){int m = nums1.size(), n = nums2.size(),i=0, j=0, L=0, R=0;for(int x = 0;x <= (m+n)/2; x++){L = R;if(i<m && (j >= n || nums1[i] < nums2[j]))	// j >= n：包含了边界问题{R = nums1[i];i++;}else{R = nums2[j];j++;}}// % 取余，为1是奇数，R值为中位数，L为其上一个数；为0是偶数，R/L为中位数两端的数return (m+n)%2 ? R: (R+L)/2.0;}	
};