NC36. 在两个长度相等的排序数组中找到上中位数
描述
示例1
输入:
[1,2,3,4],[3,4,5,6]
输出:
3
说明:
总共有8个数，上中位数是第4小的数，所以返回3。示例2
输入:
[0,1,2],[3,4,5]
输出:
2
说明:
总共有6个数，那么上中位数是第3小的数，所以返回2示例3
输入:
[1],[2]
输出:
1
C++ 解法, 执行用时: 25ms, 内存消耗: 5788KB, 提交时间: 2021-12-18
static const auto io_sync_off=[](){//c++11特性的匿名函数
ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
int l1=0,r1=arr1.size()-1,l2=0,r2=arr2.size()-1;
while(l1<r1){
int m1=(l1+r1)/2;
int m2=(l2+r2)/2;
int k=r1-l1+1;//arr1的个数
if(arr1[m1] == arr2[m2])
return arr1[m1];
else if(arr1[m1] > arr2[m2]){
if(k%2 == 0){
r1=m1;
l2=m2+1;
}
else{
r1=m1;
l2=m2;
}
}
else if(arr1[m1] < arr2[m2]){
if(k%2 == 0){
r2=m2;
l1=m1+1;
}
else{
r2=m2;
l1=m1;
}
}
}
return min(arr1[l1],arr2[l2]);
}
};
C++ 解法, 执行用时: 26ms, 内存消耗: 5828KB, 提交时间: 2021-10-06
static const auto io_sync_off=[](){//c++11特性的匿名函数
ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
int i=0,j=0,n=arr1.size(),ans;//i，j作为双指针指向两个数组首端元素
while(i+j<n){//到遍历过的总元素i+j等于总数组长度一半n时，即找到中位数
if(arr1[i]<arr2[j])ans=arr1[i++];//ans每次记录较小值，并令指针后移
else ans=arr2[j++];
}
return ans;//返回中位数
}
};
C++ 解法, 执行用时: 26ms, 内存消耗: 7228KB, 提交时间: 2022-01-07
static const auto io_sync_off=[](){//c++11特性的匿名函数
ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return nullptr;
}();
class Solution {
public:
/**
* find median in two sorted array
* @param arr1 int整型vector the array1
* @param arr2 int整型vector the array2
* @return int整型
*/
int getElement(vector<int> &arr1, vector<int> &arr2, int k)
{
int sizeA = arr1.size();
int sizeB = arr2.size();
int indexA = 0; int indexB = 0;
while(true)
{
if(indexA > sizeA -1)
return arr2[indexB + k - 1];
if(indexB > sizeB -1)
return arr1[indexA + k - 1];
if(k == 1)
return min(arr1[indexA], arr2[indexB]);
int newindexA = min(indexA + k / 2 - 1, sizeA - 1);
int newindexB = min(indexB + k / 2 - 1, sizeB - 1);
if(arr1[newindexA] <= arr2[newindexB])
{
k = k - (newindexA - indexA + 1);
indexA = newindexA + 1;
}
else
{
k = k - (newindexB - indexB + 1);
indexB = newindexB + 1;
}
}
}
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
// write code here
int totalsize = arr1.size() + arr2.size();
return getElement(arr1, arr2, totalsize/2);
}
};
C++ 解法, 执行用时: 27ms, 内存消耗: 5780KB, 提交时间: 2021-11-27
static int x = []{
std::ios::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}();
class Solution {
public:
/**
* find median in two sorted array
* @param arr1 int整型vector the array1
* @param arr2 int整型vector the array2
* @return int整型
*/
int getKthElement(vector<int>& arr1, vector<int>& arr2, int k){
int n1 = arr1.size(), n2 = arr2.size();
int idx1 = 0, idx2 = 0;
while(true){
if(idx1 == n1) return arr2[k-1];
if(idx2 == n2) return arr1[k-1];
if(k == 1) return min(arr1[idx1], arr2[idx2]);
int half = k /2;
int nidx1 = min(idx1+half, n1)-1;
int nidx2 = min(idx2+half, n2)-1;
if(arr1[nidx1] < arr2[nidx2]){
k -= (nidx1 - idx1) +1;
idx1 = nidx1 + 1;
} else{
k -= (nidx2 - idx2) +1;
idx2 = nidx2 + 1;
}
}
return -1;
}
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
// write code here
int n1 = arr1.size(), n2 = arr2.size();
return getKthElement(arr1, arr2, (n1 + n2) / 2);
}
};
C++ 解法, 执行用时: 28ms, 内存消耗: 5772KB, 提交时间: 2021-11-03
class Solution {
public:
/**
* find median in two sorted array
* @param arr1 int整型vector the array1
* @param arr2 int整型vector the array2
* @return int整型
*/
int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2)
{
int id1 = 0;
int id2 = 0;
int mid = 0;
int N = arr1.size();
arr1.push_back(2000000000);//哨兵
arr2.push_back(2000000000);//哨兵
while (id1 < N || id2 < N)
{
if (arr1[id1] < arr2[id2])
{
mid = arr1[id1];
++id1;
}
else
{
mid = arr2[id2];
++id2;
}
if (id1 + id2 == N)
{
break;
}
}
return mid;
}
};
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();