餐馆网站怎么做,自己创建网站怎么赚钱,如何零基础学编程,微信机器人与wordpress目录
方法一#xff1a; 方法二#xff1a; 方法三#xff1a; 方法四#xff1a;
没有讲解#xff0c;但给出了优秀题解 本题链接#xff1a;4. 寻找两个正序数组的中位数 - 力扣#xff08;LeetCode#xff09; 话不多说#xff0c;我们直接开始进行本题的思路解…目录
方法一 方法二 方法三 方法四
没有讲解但给出了优秀题解 本题链接4. 寻找两个正序数组的中位数 - 力扣LeetCode 话不多说我们直接开始进行本题的思路解析
首先我们看到这个题是肯定有一种暴力的硬解思路的
方法一
那就是将两个vector直接链接起来然后再排序后直接返回中间值这个方法实现起来还是非常容易的 代码如下 class Solution {
public:double findMedianSortedArrays(vectorint nums1, vectorint nums2){size_t n nums1.size();size_t m nums2.size();if (m 0){if (n % 2 0)return (nums1[n / 2 - 1] nums1[n / 2]) / 2.0;elsereturn nums1[n / 2];}if (n 0){if (m % 2 0)return (nums2[m / 2 - 1] nums2[m / 2]) / 2.0;elsereturn nums2[m / 2];}size_t sum m n;int* nums new int[m n];int count 0, i 0, j 0;while (count ! sum){if (i n){while (j ! m)nums[count] nums2[j];break;}if (j m){while (i ! n)nums[count] nums1[i];break;}if (nums1[i] nums2[j])nums[count] nums2[j];elsenums[count] nums1[i];}if (count % 2 0)return (nums[count / 2 - 1] nums[count / 2]) / 2.0;elsereturn nums[count / 2];}
};int main()
{vectorint s1;vectorint s2;s1.push_back(1);s1.push_back(2);s2.push_back(3);s2.push_back(4);s2.push_back(5);s2.push_back(6);Solution s;cout s.findMedianSortedArrays(s1, s2) endl;return 0;
} 首先这个代码是可以编译成功的 这里也有一个小技巧如果这个代码是为0那么证明编译时没有问题的如果是非0那么就是编译有问题还需要修改代码。 但是会过来这个代码再力扣上是运行超时的因为题目要求的时间复杂度是O(log (mn)) 但是我们的时间复杂度是O(mn) 空间复杂度也是O(mn) 方法二
其实我们的方法一是我们真正的将两个vector真正的链接在了一起但实际上我们这一步可以省略我们只需要挨个比较得到第k假设中位数为第k位个大的数是多少那么其实就得到了中位数是多少。其实这一题方便了一点题目给的数组是已有序的所以我们挨个比较就行
开始我们写一个循环这个循环我们的目的就是找到中位数所对应的下标是多少如果找到了那么就返回他的下标值还没找到那么就继续。但是这样来说对偶数和奇数的分类会很麻烦。当其中一个数组遍历完后还要分好几种情况进行另类判断另一个数组这样想起来都麻烦。
然而要进行优化那么我们就需要找到要进行优化的部分那么就是考虑对偶与奇的情况不分开讨论进行合并考虑对于此情况我们可以在另定义两个变量left与right分别保存左操作数与右操作数。
假设合并的数组长度为len那么无论对应偶还是奇我们只需要遍历前 len/21 个数就可以如果是偶数我们需要知道第 len/2和 len/21 个数也是需要遍历 len/21 次。所以遍历的话奇数和偶数都是 len/21 次。
返回的left与right我们要做到如果是奇那么只需要right如果是偶因为left不等于right所以返回两个数的平均数所以我们在for循环里应该保证依次循环过后left与right差一个位所以我们要先在循环开始将right的值赋给left后进行调整right。
然后写出大致框架
如果nums1[i]nums2[i],那么就将nums1[i]赋值给right反之nums2[i];
我们在调整right的时候首先要考虑的就是nums是否越界所以我需要先判断是否越界同理考虑了nums1也需要考虑nums2 所以填充完代码如下 class Solution {
public:double findMedianSortedArrays(vectorint nums1, vectorint nums2) {int m nums1.size();int n nums2.size();int len m n;int left -1, right -1;int aStart 0, bStart 0;for (int i 0; i len / 2; i) {left right;//调整rightif (aStart m (bStart n || nums1[aStart] nums2[bStart])) {right nums1[aStart];}else {right nums2[bStart];}}if ((len % 2) 0)return (left right) / 2.0;elsereturn right;}
};
int main()
{vectorint s1;vectorint s2;s1.push_back(1);s1.push_back(2);s2.push_back(3);s2.push_back(4);s2.push_back(5);s2.push_back(6);Solution s;cout s.findMedianSortedArrays(s1, s2) endl;return 0;
} 运行起来是正确的但依然在力扣上是不行的还是运行超时 时间复杂度是遍历了mn/21个数但时间复杂度还是O(mn) 方法三 我第一眼看到这个题的时候首先想到的就是二分查找然后就想到了分别对两个数组进行二分但是如果nums2全都大于num1那么这样就不行然后我在看了别人的题解后然后理解了理解就大为震撼妙但是题解是java的然后我自己又写了写修改了好几次终于写出来了。
方法二中我们一次遍历就相当于去掉不可能是中位数的一个值也就是一个一个排除。由于数列是有序的其实我们完全可以一半儿一半儿的排除。假设我们要找第 k 小数我们可以每次循环排除掉 k/2 个数。方法三其实与方法二同理也是主要找到第k个数是多少。
下面我们看一个例子 此时33
然后我们需要将两个数组的第 k/2 个数进行比较 然后将小的那个数组前k/2个数舍弃对于方便处理我们设定如果两个数相等目前我们先优先删除第二个数组删除后面代码是是先有限舍弃第一个数组这里是为了避开特殊情况 此时15
这次舍弃num1 的 k/2 个数 此时25
同理继续舍弃nums1舍弃 k/2 个数 这时候35这时候3就为第6大的数就是中位数。
这个方法是不是很妙呢
然后我们就刷刷的写然后突然就有一个案例不通过那就是
如果按照上面的方法进行按照步骤进行梳理那么就会发现第一步的时候就会卡住因为第一步我么要进行舍弃的数的个数就已经超出了nums1的长度直接会越界那么这时候我们就需要进行特殊处理如果舍弃个数大于剩余长度那么就舍弃剩余长度。 思路全部梳理完后如果对递归熟悉的话那么就完全可以写出来思路难想但是代码实现还是比较简单的。特殊案例我也进行处理了后面会进行特别分析
class Solution {
public:double findMedianSortedArrays(vectorint nums1, vectorint nums2) {int n nums1.size();int m nums2.size();int left (n m 1) / 2;int right (n m 2) / 2;return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;}int getKth(vectorint nums1, int start1, int end1, vectorint nums2, int start2, int end2, int k){//舍弃k/2个//结束条件k1int len1 end1 - start1 1;int len2 end2 - start2 1;//让 len1 的长度小于 len2这样就能保证如果有数组空了一定是 len1 if (len1 len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);//还存在一种情况就是k不为1的情况下但len1已经等于0if (len1 0) return nums2[start2 k - 1]; if (k 1)return min(nums1[start1], nums2[start2]);int i start1 min(len1, k / 2) - 1;int j start2 min(len2, k / 2) - 1;if (nums1[i] nums2[j]){return getKth(nums1, start1, end1, nums2, j 1, end2, k - (j - start2 1));}else{return getKth(nums1, i 1, end1, nums2, start2, end2, k - (i - start1 1));}}
};
到此我们就出来了第一种在力扣上通过的代码
然后进行特别分析 1
这一步也是跟方法二同样的找到求中位数的操作数第left是第几个right是第几个与之不同的就是奇的情况下leftright偶的情况下left1right 2 此案例对应的也就是 在求right的时候k7先舍弃k/23个
此时k4
然后再舍弃的话num1已经没有了但是k4-22还不为1如果返回的还要再舍弃的话就会报错越界
所以要加特殊情况处理 3
这一步也是为了对应2方便如果没有这个那么就有可能len2先空的情况所以这一步避免了分类讨论 最后再展示一边代码 class Solution {
public:double findMedianSortedArrays(vectorint nums1, vectorint nums2) {int n nums1.size();int m nums2.size();int left (n m 1) / 2;int right (n m 2) / 2;return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;}int getKth(vectorint nums1, int start1, int end1, vectorint nums2, int start2, int end2, int k){//舍弃k/2个//结束条件k1int len1 end1 - start1 1;int len2 end2 - start2 1;//让 len1 的长度小于 len2这样就能保证如果有数组空了一定是 len1 if (len1 len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);//还存在一种情况就是k不为1的情况下但len1已经等于0if (len1 0){return nums2[start2 k - 1];}if (k 1)return min(nums1[start1], nums2[start2]);int i start1 min(len1, k / 2) - 1;int j start2 min(len2, k / 2) - 1;if (nums1[i] nums2[j]){return getKth(nums1, start1, end1, nums2, j 1, end2, k - (j - start2 1));}else{return getKth(nums1, i 1, end1, nums2, start2, end2, k - (i - start1 1));}}
}; 运行成功 时间复杂度是O(log (mn)) 。符合要求 方法四
但是这个方法三还是效率不是很高
其实还有一种更牛的方法但本人看了看看不明白运用到了统计学本人还没有学统计学能看明白一点但是还是看清楚
我看了题解有两种一个数官方一个是别的作者大佬写的本人推荐大佬官方直接给了题目解释没有给知识补充
4. 寻找两个正序数组的中位数 - 力扣LeetCode
为了方便这里给出了全部官方截图 最后这个题就已经完全讲解完了第一次完全写完力扣困难题总的来说是很难但不至于一点思路也没有而且写的过程中思考是很多的还是比简单题写起来吃力。有能力还是多写困难题
