做损坏文档的网站,asp网站搭建教程,游戏怎么制作,建筑网站do题目#xff1a; 给定两个大小分别为 m 和 n 的正序#xff08;从小到大#xff09;数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 解法1、暴力解法#xff08;归并#xff09; 思路#xff1a; 合并 nums1#xff0c;nums2 为第三个数组 排序第三个数…题目 给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 解法1、暴力解法归并 思路 合并 nums1nums2 为第三个数组 排序第三个数组 按下标找出中位数
class Solution
{
public:double findMedianSortedArrays(vectorint nums1,vectorint nums2){int m nums1.size(), n nums2.size(), k0, i0, j0;vectorint result(mn,0);while(im jn){if(nums1[i] nums2[j]){result[k] nums1[i];i;}else{result[k] nums2[j];j;}k;}// nums1或nums2有一个已经遍历完while(im){result[k] nums1[i];i;k;}while(jn){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(vectorint nums1,vectorint nums2){int m nums1.size(), n nums2.size(),i0, j0, L0, R0;for(int x 0;x (mn)/2; x){L R;if(im (j n || nums1[i] nums2[j])) // j n包含了边界问题{R nums1[i];i;}else{R nums2[j];j;}}// % 取余为1是奇数R值为中位数L为其上一个数为0是偶数R/L为中位数两端的数return (mn)%2 ? R: (RL)/2.0;}
};解法3二分查找法 此题用二分查找法不好理解放弃 建议使用暴力归并法和双指针法解题
