网站团队人数,网站开发一个页面多少钱,WordPress page filed,wordpress作伪静态网页404题目链接#xff1a;4. 寻找两个正序数组的中位数 - 力扣#xff08;LeetCode#xff09;
一、题目分析 这道题目是让我们在 两个正序的数组中寻找中位数已知两个数组的大小分别是#xff1a;int m nums1.size(),n nums2.size();中位数性质1#xff1a;中位数左侧元素 …题目链接4. 寻找两个正序数组的中位数 - 力扣LeetCode
一、题目分析 这道题目是让我们在 两个正序的数组中寻找中位数已知两个数组的大小分别是int m nums1.size(),n nums2.size();中位数性质1中位数左侧元素 ≤ 中位数 且 中位数右侧元素 ≥ 中位数 以升序来看中位数性质2对于一个长度为 N 的数组中位数将数组一分为二使得左侧与右侧得元素长度差 ≤ 1当 m n 为奇数时我们需要找到合并后数组中第 k 1 小的元素其中 k (m n) / 2。当 m n 为偶数时我们需要找到合并后数组中第 k 和第 k 1 小的元素然后计算它们的平均值其中 k (m n) / 2 - 1注意这里 k 是基于 0 的索引所以实际要找的元素位置是 k 和 k 1。
二、算法原理讲解
解法一暴力排序
通过合并排序的原理通过中位数的性质可快速得到中位数的下标较为简单
时间复杂度为O(MN)空间复杂度为O(MN)
解法二双指针
时间复杂度为O(MN)空间复杂度为O(1)
解法三暴力枚举
解法四二分优化 三、编写代码
class Solution {
public:double findMedianSortedArrays(vectorint nums1, vectorint nums2) {int m nums1.size(), n nums2.size();if(m n) swap(nums1,nums2); // 保证nums1始终是较短数组int k (m n 1) / 2; // 应划分给小数组的个数// 枚举 i [0,m]for(int i 0;i m;i){int j k - i;// 分割线周围的四个值int a i m ? INT_MAX :nums1[i];int b i 0 ? INT_MIN :nums1[i-1];cout i j endl;int c j n ? INT_MAX :nums2[j];int d j 0 ? INT_MIN :nums2[j-1];// 分割线是否合法if(b c d a){if((m n) % 2 1) return max(b,d);else return (double)(max(b,d) min(c,a)) / 2;}}return 1314.521;}
}; class Solution {
public:double findMedianSortedArrays(vectorint nums1, vectorint nums2) {// 保证nums1始终是较短数组if(nums1.size() nums2.size()) swap(nums1,nums2);// 应划分给小数组的个数int k (nums1.size() nums2.size() 1) / 2; // 枚举nums1数组中应该划分给小数组的元素个数二分优化int left 0,right nums1.size();while(left right){// mid ∈ [0,m]int i (left right 1) / 2; int j k - i;cout i endl;if(nums1[i-1] nums2[j]) left i;else right i - 1;}// 分割线两边的值int a left nums1.size() ? INT_MAX :nums1[left];int b left 0 ? INT_MIN :nums1[left-1];int c (k-left) nums2.size() ? INT_MAX :nums2[k-left];int d (k-left) 0 ? INT_MIN :nums2[k-left-1];// 处理数据返回if((nums1.size() nums2.size()) % 2 1) return max(b,d);else return (double)(max(b,d) min(c,a)) / 2;}
};
