leetcode热题100-4——寻找两个正序数组的中位数
目录
- 前言
- 正文
- 题目
- 参考
前言
正文
题目
未看题解时,解题的思路
该题暴力解法肯定是很舒服的,不过,该题要求算法的时间复杂度为O(log(m+n))就还是挺难的。
自己实现的代码
自己的暴解就不贴了,贴一个人家实现的算法。
看了题解后解题的思路
- 方法一:就是用两个临时变量,middle1=MIN middle2 = MAX,用这两个来记录该数组的中间两个元素,若是偶数个元素,就相加除2。若是奇数个元素,则直接返回Middle2就可以了。时间复杂度仍是 O(m+n)。这个方法是不太满足进阶的要求的。确实要求O(log(m+n))的方法是比较难的,所以,等以后有时间,再返回解决。寻找两个正序数组的中位数 答案
标准答案的代码
方法一:code
class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int size1 = nums1.size();int size2 = nums2.size();int totalSize = size1+size2;int middle1 = INT_MIN;int middle2 = INT_MAX;int index1 = 0;int index2 = 0;for(int i = 0;i<=totalSize/2;i++){middle1 = middle2;if(index2>=size2||(index1<size1&&nums1[index1]<nums2[index2]))middle2 = nums1[index1++];elsemiddle2 = nums2[index2++];}if((totalSize%2)==0)return (middle1+middle2)/2.0;elsereturn middle2;}
};
这是我的分析过程,可供参考
参考
- 力扣热题100
leetcode热题100-4——寻找两个正序数组的中位数
目录
- 前言
- 正文
- 题目
- 参考
前言
正文
题目
未看题解时,解题的思路
该题暴力解法肯定是很舒服的,不过,该题要求算法的时间复杂度为O(log(m+n))就还是挺难的。
自己实现的代码
自己的暴解就不贴了,贴一个人家实现的算法。
看了题解后解题的思路
- 方法一:就是用两个临时变量,middle1=MIN middle2 = MAX,用这两个来记录该数组的中间两个元素,若是偶数个元素,就相加除2。若是奇数个元素,则直接返回Middle2就可以了。时间复杂度仍是 O(m+n)。这个方法是不太满足进阶的要求的。确实要求O(log(m+n))的方法是比较难的,所以,等以后有时间,再返回解决。寻找两个正序数组的中位数 答案
标准答案的代码
方法一:code
class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int size1 = nums1.size();int size2 = nums2.size();int totalSize = size1+size2;int middle1 = INT_MIN;int middle2 = INT_MAX;int index1 = 0;int index2 = 0;for(int i = 0;i<=totalSize/2;i++){middle1 = middle2;if(index2>=size2||(index1<size1&&nums1[index1]<nums2[index2]))middle2 = nums1[index1++];elsemiddle2 = nums2[index2++];}if((totalSize%2)==0)return (middle1+middle2)/2.0;elsereturn middle2;}
};
这是我的分析过程,可供参考
参考
- 力扣热题100