NC252. 多数组中位数
描述
给定两个升序的数组 arr1 和 arr2 ，求两个数组合并后的下中位数
注意：下中位数指在两个数组的数个数在偶数时取更小的
数据范围：两个数组的长度都满足 
，数组中的所有值都满足 
示例1
输入:
[1,2,3],[3,4,5]
输出:
3
示例2
输入:
[1,2,3],[4,5]
输出:
3
NC252. 多数组中位数
描述
示例1
输入:
[1,2,3],[3,4,5]
输出:
3
示例2
输入:
[1,2,3],[4,5]
输出:
3
C++ 解法, 执行用时: 126ms, 内存消耗: 37480KB, 提交时间: 2022-07-11
static const auto io_sync_off = [](){
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int getUpMedian(vector<int>& arr1, vector<int>& arr2) {
int i=0,j=0;
int res;
int c=0;
int k;
if((arr1.size()+arr2.size())%2==0)
k=(arr1.size()+arr2.size())/2;
else k=(arr1.size()+arr2.size())/2+1;
while(i<arr1.size()||j<arr2.size())
{
if(c==k)
break;
if(i==arr1.size())
res=arr2[j++];
else if(j==arr2.size())
res=arr1[i++];
else
{
if(arr1[i]>arr2[j])
res=arr2[j++];
else res=arr1[i++];
}
c++;
}
return res;
}
};
C++ 解法, 执行用时: 219ms, 内存消耗: 37452KB, 提交时间: 2022-02-10
class Solution {
public:
/*
题意整理
给定两个升序的数组arr1和arr2。
求这两个数组合并后的下中位数。
方法一：归并
解题思路
本题需要求两个有序数组合并后的下中位数，假设合并后数组的长度为m+n，
则下中位数刚好是新数组中第(m+n)/2小的数，令K等于(m+n)/2，则可以将问题转化为求新数组中恰好第K小的数。
1. 执行K次循环，每次将较小的值赋值给res。
2. 新建两个变量id1、id2，id1是arr1数组游标，id2是arr2数组游标。
如果id1和id2都没有到末尾，将两者指向的值中较小的赋值给res，并后移游标。
3. 如果id1到达末尾，则继续将arr2数组的值赋值给res。否则，将arr1数组的值赋值给res。
复杂度分析
时间复杂度：需要给res赋值K次，循环总共执行K次，而K为m+n的一半，所以时间复杂度是O(m+n)
空间复杂度：需要额外常数级别的空间，所以空间复杂度为O(1)O(1)O(1)。
*/
int getUpMedian(vector<int>& arr1, vector<int>& arr2) {
int m = arr1.size();
int n = arr2.size();
//用于记录结果
int res = 0;
//id1是arr1数组游标，id2是arr2数组游标
int id1 = 0, id2 = 0;
int K = (m + n) / 2;
//循环K次，每次将较小的值赋值给res，最后res一定是第K小的数
while(K-- > 0){
//如果id1和id2都没有到末尾
if(id1 < m && id2 < n){
//将两者中较小的赋值给res，并后移游标
if(arr1[id1] < arr2[id2]){
res = arr1[id1++];
}
else{
res = arr2[id2++];
}
}
//如果id1到达末尾，则继续将arr2数组的值赋值给res
else if(id1 == m){
res = arr2[id2++];
}
//否则，将arr1数组的值赋值给res
else{
res = arr1[id1++];
}
}
return res;
}
};
C++ 解法, 执行用时: 220ms, 内存消耗: 37348KB, 提交时间: 2021-12-20
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param arr1 int整型vector
* @param arr2 int整型vector
* @return int整型
*/
int getUpMedian(vector<int> const& arr1, vector<int> const& arr2);
};
static pair<int, int> part(vector<int> const& arr, int index) {
return make_pair(index ? arr[index-1] : INT_MIN,
index < int(arr.size()) ? arr[index] : INT_MAX);
}
int Solution::getUpMedian(vector<int> const& arr1, vector<int> const& arr2) {
if (arr1.size() > arr2.size()) return getUpMedian(arr2, arr1);
int lo = 0, hi(arr1.size() + 1), half((1 + arr1.size() + arr2.size()) >> 1);
while (lo < hi) {
int mid1 = (lo + hi) >> 1, mid2 = half - mid1;
auto [l1, h1] = part(arr1, mid1);
auto [l2, h2] = part(arr2, mid2);
int l_num = max(l1, l2), h_num = min(h1, h2);
if (l_num <= h_num) return l_num;
if (l1 > h2) hi = mid1;
else lo = mid1 + 1;
}
return -1;
}
C++ 解法, 执行用时: 227ms, 内存消耗: 37352KB, 提交时间: 2021-12-18
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param arr1 int整型vector
* @param arr2 int整型vector
* @return int整型
*/
int getUpMedian(vector<int>& arr1, vector<int>& arr2) {
// write code here
int len1=arr1.size(),len2=arr2.size();
int count=(len1+len2)/2+1;
vector<int> tmp;
int i=0,j=0;
while(count--){
if(arr1[i]<arr2[j]){
tmp.push_back(arr1[i]);
i++;
}
else{
tmp.push_back(arr2[j]);
j++;
}
}
if((len1+len2)%2==0)
return *(tmp.end()-2);
return *(tmp.end()-1);
}
};
C++ 解法, 执行用时: 230ms, 内存消耗: 37452KB, 提交时间: 2022-01-23
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param arr1 int整型vector
* @param arr2 int整型vector
* @return int整型
*/
int getUpMedian(vector<int>& arr1, vector<int>& arr2) {
// write code here
int len=(arr1.size()+arr2.size())/2;
if(((arr1.size()+arr2.size())&1)==0){
len--;
}
return findKthNum(arr1,arr2, len+1);
}
int GetMidNum(vector<int>&nums1,int start1,int end1,vector<int>&nums2,int start2,int end2){
int mid1=0;
int mid2=0;
int offset=0;
while(start1<end1){
mid1=(end1+start1)/2;
mid2=(end2+start2)/2;
offset=((end1-start1+1)&1)^1;
if(nums1[mid1]>nums2[mid2]){
end1=mid1;
start2=mid2+offset;
}
else if(nums1[mid1]<nums2[mid2]){
start1=mid1+offset;
end2=mid2;
}
else{
return nums1[mid1];
}
}
return min(nums1[start1],nums2[start2]);
}
int findKthNum(vector<int>&arr1,vector<int>&arr2,int k){
vector<int>longs=arr1.size()>=arr2.size()?arr1:arr2;
vector<int>shorts=arr1.size()<arr2.size()?arr1:arr2;
int shortLenth=shorts.size();
int longLenth=longs.size();
if(k<=shortLenth){
return GetMidNum(shorts,0,k-1,longs,0,k-1);
}
if(k>longLenth){
if(shorts[k-longLenth-1]>=longs[longLenth-1]){
return shorts[k-longLenth-1];
}
if(longs[k-shortLenth-1]>=shorts[shortLenth-1]){
return longs[k-shortLenth-1];
}
return GetMidNum(shorts,k-longLenth,shortLenth-1,longs,k-shortLenth,longLenth-1);
}
if(longs[k-shortLenth-1]>=shorts[shortLenth-1]){
return longs[k-shortLenth-1];
}
return GetMidNum(shorts,0,shortLenth-1,longs,k-shortLenth,k-1);
}
};