渭南中学校园网站建设工作汇报,产品网站设计论文,wordpress 4.6漏洞,网站轮播图怎么保存思路一#xff08;暴力#xff09;#xff1a; 当看到这个题目的时候可能会觉的是不是系统高估了这个题目#xff0c;这个这么简单#xff0c;只需要将两个数组合并#xff0c;排序然后合并就好了。这样做确实可以求出中位数#xff0c;但是并不能说是完成题目的要求暴力 当看到这个题目的时候可能会觉的是不是系统高估了这个题目这个这么简单只需要将两个数组合并排序然后合并就好了。这样做确实可以求出中位数但是并不能说是完成题目的要求因为题目的要求时间复杂度是O(log(m n))这个暴力算法的时间复杂度很明显是O(mn)可以有兴趣的可以测一下这个算法不是本博客的重点这里不多赘述代码如下 double findMedianSortedArrays(vectorint nums1, vectorint nums2) {double ret -1;vectordouble buff;//合并两个数组for (auto e : nums1)buff.push_back(e);for (auto a : nums2)buff.push_back(a);//将合并后的结果进行排序sort(buff.begin(), buff.end());int size3 buff.size();//获取中位数if (size3 % 2 0){ret ((buff[size3 / 2] buff[size3 / 2 - 1]) / 2);}elseret buff[size3 / 2];return ret;
}思路二分治二分查找
题目解析 这个题目简单来说就是如果将两个已经排序的数组合并为一个虚拟数组求出这个虚拟数组的中位数即可。
解题思路 1、这道题最主要的就是切cut怎么将数组切成合适的两段是关键对于一个数组来说在数组的中间将其切成两段这时候就要分情况讨论如果是偶数个中位数就是切点的两边第一个数的平均值如果是奇数个中位数就是切点右边的第一个数比如说1 2 3 4 5在中间的位置将这个数组切成两段1 2 \ 3 4 5很显然中位数就是3如果是1 2 3 4那么就切成了1 2 \ 3 4很显然中位数就是(23)/2 2.5。 2、理解了切的思想接下来就开始在两个数组中进行切这时候就用到了分治思想。 怎么分 题目中要求的时间复杂度为 O(log(m n))很容易想到的方法就是二分现在有两个数组要对那个数组进行二分合适由于找的是中位数那么这个数字的两边的元素个数是相等的所以只需要确定一个数组中的两边元素两一个数组的对应的补上去就可以了为了提高效率要选择最短的数组做二分查找。 怎么治 这个也很容易只需要分别比较两个数组切点两边的数就可以假设数组1中切点两边的元素为L1R1数组2中切点两边的元素为L2R2切完之后有三种情况 1L1R2 说明数组1的左半边比数组2的右半边大应该让cut向左移才能使数组一中较多的数被分配到右边。 2L2R1 说明数组2的左半边比数组1的右半边大应该让cut向右移才能使数组一中较多的数被分配到左边。 3其他情况L1R2 L2R1cut的位置是正确的可以停止查找输出结果。 3.特殊情况 分析完了正常的情况那么就要分析一下特殊情况 1)如果有一个数组是空的直接返回另一个不为空的数组中的中位数 2)如果两个数组元素的个数相等并且两个数组的中位数相等直接返回其中一个中位数。 3)有可能在进行二分查找的时候出现了数组越界的情况只需要定义一个最大值和一个最小值这样可以按照正常的情况来处理了。 4、输出结果分情况 两个数组的输出情况和之前的一个数组的输出大致是一样只是添加了选择性如果是偶数个输出(min(L1, L2) min(R1, R2))/2如果是奇数个输出min(R1, R2)。
图解思路 这里只对不越界和不为空的数组进行解析。
代码解析
class Solution {
public:double MedNum(vectorint num){double ret;size_t size num.size();if(size 1)return num[0];int med size / 2;if (size% 2 0){ret ((double)(num[med] num[med - 1]) / 2);}elseret num[med];return ret;}double findMedianSortedArrays(vectorint nums1, vectorint nums2){double ret -1;//定义最小数和最大数const int BDL_MIN_ 0x80000000;const int BDL_MAX_ 0x7fffffff;//情况一//如果这两个数组中有一个是空的直接返回另一个的中位数即可if (nums1.empty())return MedNum(nums2);else if (nums2.empty())return MedNum(nums1);//情况二//如果两个数组分别的中位数相等那么这两个数的中位数就是这个中位数int size1 nums1.size(); //数组一的长度int size2 nums2.size(); //数组二的长度if(size1 size2){Med1 MedNum(nums1);Med1 MedNum(nums1);if(Med1 Med2)return Med1;}//情况三//使用分治思想二分查找方法int size0 size1 size2; //两个数组的总长度//为了效率要选择最短的数组做二分查找使数组一为最短//如果第一个数组比第二个数组长就要使两个数组交换//但是swap的时间复杂度使O(NM),所以将两个数组交换位置再调一次函数即可if (size1 size2)return findMedianSortedArrays(nums2, nums1);//设置二分查找的范围int cutL 0;int cutR size1;//这里将cut1初始为数组1的中位数int cut1 (size1 - 1) / 2;while (cut1 size1){cut1 (cutR - cutL) / 2cutL; //在数组1中找cut1切点二分int cut2 (size0 / 2) - cut1; //在数组2中找cut2切点//这里不用size2直接确定切点是因为将两个数组进行了虚拟合并使用虚拟数组的总数size0找中间点然后将属于数组一的部分减去就是cut2在数组2中的切点可以结合上面的图片捋一下。//确定L1,L2,L3,L4的值并判断当前的切点有没有越界 double L1 (cut1 0) ? BDL_MIN_ : nums1[cut1-1];double R1 (cut1 size1) ? BDL_MAX_ : nums1[cut1];double L2 (cut2 0) ? BDL_MIN_ : nums2[cut2-1];double R2 (cut2 size2) ? BDL_MAX_ : nums2[cut2];//如果L1R2则cut1应该向左移才能使数组1较多的数被分配到右边。if (L1 R2)cutR cut1-1;//如果L2 R1则cut1应该向右移才能使数组1较多的数被分配到左边。else if (L2 R1)cutL cut11;//其他情况就是L1R2 L2R1说明当前cut1和cut2的位置就是中位数的位置了else{//如果两个数组中加起来的元素数量是偶数那么中位数就应该是两个中位数的平均值if (size0 % 2 0){L1 max(L1, L2);R1 min(R1, R2);ret (L1 R1) / 2;return ret;}//如果两个数组中元素的数量是奇数中位数就是当前位置的右值else{ret min(R1, R2);return ret;}}}return ret;}
};如果有什么问题可以在评论区留言
