寻找2个正序数组的中位数
2021-11-03 本文已影响0人
一枚懒人
4：寻找两个正序数组的中位数
题目：
给定两个大小分别为
m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的 中位数
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
自行解答
double mediaNum = 0;
void computeMediaNum(bool isSingular,
int currentPos,int currentValue,int medianPos){
if(isSingular){
if(currentPos == medianPos){
mediaNum = currentValue;
}
} else{
if(currentPos == medianPos){
mediaNum += currentValue;
}
if( currentPos == medianPos+1){
mediaNum += currentValue;
mediaNum /= 2.0;
}
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
list<int> allNums;
vector<int>::iterator it1 = nums1.begin();
vector<int>::iterator it2 = nums2.begin();
int allNumsLength = nums1.size() +nums2.size();
int mediaNumsPos = -1;
bool isSingular = false;
list<int>::iterator listIt = allNums.begin();
if(allNumsLength %2 == 0){
mediaNumsPos = allNumsLength / 2 - 1;
} else{
isSingular = true;
mediaNumsPos = allNumsLength / 2;
}
int listCount = 0;
while (true){
if(it1 == nums1.end() && it2 == nums2.end()){
break;
}
if(it1 == nums1.end()){
*listIt = *it2;
computeMediaNum(isSingular, listCount, *listIt, mediaNumsPos);
if(listCount >= mediaNumsPos + 1){
break;
}
listIt ++;
it2++;
listCount++;
continue;
}
if(it2 == nums2.end()){
*listIt = *it1;
computeMediaNum(isSingular, listCount, *listIt, mediaNumsPos);
if(listCount >= mediaNumsPos + 1){
break;
}
listIt ++;
it1++;
listCount++;
continue;
}
if(*it1 > *it2){
*listIt = *it2;
it2++;
} else{
*listIt = *it1;
it1++;
}
computeMediaNum(isSingular, listCount, *listIt, mediaNumsPos);
if(listCount >= mediaNumsPos + 1){
break;
}
listIt++;
listCount++;
}
return mediaNum;
}
思路分析：
- 根据输入的2个vector 的长度，确认中位数的所在位置（单双数位置不同）
- 构建存放输出结果的目标vector，获取2个入参的vector的迭代器，开始遍历2个数组
- 2.1 如果出现2个入参中的一个已经遍历完成，则直接将未完成的另一个入参挂到目标的vector上，同时在每次迭代时，检查目标vector的位置，每次目标vector向后遍历一个位置，则检查一次是否到达了中位数所在的位置，如果达到则更新中位数
- 2.2 如果2个入参vector都没迭代到末尾，则每次比较2个数组头指针的位置，按序插入到目标vector中，同时也是每次目标vector向后遍历一个位置，则检查一次是否到达了中位数所在的位置，如果达到则更新中位数
- 结束循环的条件
- 3.1 2个入参均循环到了末尾，则循环结束（不会走此条件退出）
- 3.2 目标vector的迭代器位置超过了中位数的位置
复杂度分析
- 时间 复杂度：O((num1.size +num.size) /2),即O(N)
- 空间复杂度：开辟了list<int> allNums 因此复杂度是 O(n)
Ps:此题之所以为复杂 是因为 让时间复杂度为O(log（m+n）)
官方解答
class Solution {
public:
int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
/* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
* 这里的 "/" 表示整除
* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
* 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
* 这样 pivot 本身最大也只能是第 k-1 小的元素
* 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
* 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
* 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
*/
int m = nums1.size();
int n = nums2.size();
int index1 = 0, index2 = 0;
while (true) {
// 边界情况
if (index1 == m) {
return nums2[index2 + k - 1];
}
if (index2 == n) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return min(nums1[index1], nums2[index2]);
}
// 正常情况
int newIndex1 = min(index1 + k / 2 - 1, m - 1);
int newIndex2 = min(index2 + k / 2 - 1, n - 1);
int pivot1 = nums1[newIndex1];
int pivot2 = nums2[newIndex2];
if (pivot1 <= pivot2) {
k -= newIndex1 - index1 + 1;
index1 = newIndex1 + 1;
}
else {
k -= newIndex2 - index2 + 1;
index2 = newIndex2 + 1;
}
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int totalLength = nums1.size() + nums2.size();
if (totalLength % 2 == 1) {
return getKthElement(nums1, nums2, (totalLength + 1) / 2);
}
else {
return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
}
}
};
思路分析：
-
首先根据2个入参的vector将排序后的目标vector的长度计算出来，并且根据目标vector的长度的单双数，指定求中位数的策略 ps:此处并不是真正要进行将2个入参vector进行排序出目标vertor
-
求解2个入参vector中的第K大元素
-
排除2种情况，即num1或者 num2 遍历完成，剩下另外一个入参，不需要继续遍历，可直接求解剩下的vector中的 中位数
-
当k=1时，直接取 2个vector中当前头部数字的最小值，即代码中的
min(nums1[index1], nums2[index2]
-
最后一种情况即每次比较中位数的大小，根据二分法，如果一个小，则更新k和index1 和index2
-
复杂度分析：
时间复杂度：每次采用二分，因此时间复杂度为O(log(m+n)）
空间复杂度：采用了有限的基本变量存储，因此是O（1）
PS:
官方解法其实就是解决2个有序数组 寻找第K大数字，因为2个入参有序 寻找第K大 可直接将问题转换成寻找有序数组的第 K大数字问题。
在寻找第K大数字时，其实简单来说就是，2个数组合并之后 第K大数组 前面有k-1个数字，所以直接比较2个数组的第k/2 -1个数字大小，每次均比较这个，然后每次就会淘汰一半的数字，进一步使得时间复杂度为
O（Log（m+n）），然后每次淘汰一定数量的数字之后 问题变成了寻找第（k - 淘汰数组长度）个数字，进一步利用二分法进行查找，直到查找到 k = 1为止。
其他解法
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
if (n > m) //保证数组1一定最短
{
return findMedianSortedArrays(nums2, nums1);
}
// Ci 为第i个数组的割,比如C1为2时表示第1个数组只有2个元素。LMaxi为第i个数组割后的左元素。RMini为第i个数组割后的右元素。
int LMax1, LMax2, RMin1, RMin2, c1, c2, lo = 0, hi = 2 * n; //我们目前是虚拟加了'#'所以数组1是2*n长度
while (lo <= hi) //二分
{
c1 = (lo + hi) / 2; //c1是二分的结果
c2 = m + n - c1;
LMax1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
RMin1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2];
LMax2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
RMin2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2];
if (LMax1 > RMin2)
hi = c1 - 1;
else if (LMax2 > RMin1)
lo = c1 + 1;
else
break;
}
return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0;
}
};
int main(int argc, char *argv[])
{
vector<int> nums1 = { 2,3, 5 };
vector<int> nums2 = { 1,4,7, 9 };
Solution solution;
double ret = solution.findMedianSortedArrays(nums1, nums2);
return 0;
}
思路分析：
首先最终计算的时会填充#到数组中
其次每次分割得到的数组的2端进行比较，最终会得到mid
因为填充了#，所以填充完#的数组和原数组进行了映射，根据映射得到最终结果，忽略了原数组是奇数还是偶数的情况
详细解析请参考：
