NC413. 两个升序数组的中位数
描述
示例1
输入:
[1,2,3,4,5],[6,7,8,9]
输出:
5
示例2
输入:
[1,2,3,8,9],[4,5,6,7]
输出:
5
示例3
输入:
[1,3,4],[1,4,4]
输出:
3.5
C++ 解法, 执行用时: 30ms, 内存消耗: 3392KB, 提交时间: 2022-07-16
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums1 int整型vector
* @param nums2 int整型vector
* @return double浮点型
*/
double Median(vector<int>& nums1, vector<int>& nums2) {
// write code here
int n = nums1.size() + nums2.size();
if(n % 2){
return getKmedian(nums1, nums2, (n + 1) / 2);
}else{
return (getKmedian(nums1, nums2, n / 2 + 1) + getKmedian(nums1, nums2, n / 2)) / 2.0;
}
}
double getKmedian(vector<int>& nums1, vector<int>& nums2, int k){
int n = nums1.size();
int m = nums2.size();
int index1 = 0, index2 = 0;
while(true){
if(index1 == n){
return nums2[index2 + k - 1];
}
if(index2 == m){
return nums1[index1 + k - 1];
}
if(k == 1){
return min(nums1[index1], nums2[index2]);
}
int newindex1 = min(index1 + k / 2 - 1, n - 1);
int newindex2 = min(index2 + k / 2 - 1, n - 1);
if(nums1[newindex1] <= nums2[newindex2]){
k -= newindex1 - index1 + 1;
index1 = newindex1 + 1;
}else{
k -= newindex2 - index2 + 1;
index2 = newindex2 + 1;
}
}
}
};
C++ 解法, 执行用时: 30ms, 内存消耗: 3468KB, 提交时间: 2022-05-03
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums1 int整型vector
* @param nums2 int整型vector
* @return double浮点型
*/
double find(vector<int>& nums1, vector<int>& nums2, int k) {
// write code here
int num1_left = 0, num1_right = nums1.size() - 1;
int num2_left = 0, num2_right = nums2.size() - 1;
int num1_idx = 0;
int num2_idx = 0;
int num1_len = nums1.size();
int num2_len = nums2.size();
while (k != 1) {
int x = k / 2 - 1;
int new_num1_idx = num1_idx;
new_num1_idx = min(num1_idx + x, num1_len - 1);
int new_num2_idx = num2_idx;
new_num2_idx = min(num2_idx + x, num2_len - 1);
if (nums1[new_num1_idx] > nums2[new_num2_idx]) {
k = k - (new_num2_idx - num2_idx + 1);
num2_idx = new_num2_idx + 1;
} else {
k = k - (new_num1_idx - num1_idx + 1);
num1_idx = new_num1_idx + 1;
}
if (num2_idx >= num2_len) {
return nums1[num1_idx + k - 1];
}
if (num1_idx >= num1_len) {
return nums2[num2_idx + k - 1];
}
}
return min(nums1[num1_idx], nums2[num2_idx]);
}
double Median(vector<int>& nums1, vector<int>& nums2) {
// write code here
int num1_left = 0, num1_right = nums1.size() - 1;
int num2_left = 0, num2_right = nums2.size() - 1;
int num1_idx = 0;
int num2_idx = 0;
int num1_len = nums1.size();
int num2_len = nums2.size();
if ((num1_len + num2_len) % 2 == 1) {
return find(nums1, nums2, (num1_len + num2_len) / 2 + 1);
}
return (find(nums1, nums2, (num1_len + num2_len) / 2) + find(nums1, nums2, (num1_len + num2_len) / 2 + 1)) / 2;
}
};
C++ 解法, 执行用时: 31ms, 内存消耗: 3356KB, 提交时间: 2022-08-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums1 int整型vector
* @param nums2 int整型vector
* @return double浮点型
*/
double Median(vector<int>& nums1, vector<int>& nums2) {
// write code here
int n=nums1.size()+nums2.size();
if(n%2)
{
return getKmedian(nums1,nums2,(n+1)/2);
}else{
return (getKmedian(nums1,nums2,n/2+1)+getKmedian(nums1,nums2,n/2))/2.0;
}
}
double getKmedian(vector<int> &nums1,vector<int> &nums2,int k)
{
int n=nums1.size();
int m=nums2.size();
int index1=0,index2=0;
while(true)
{
if(index1==n)
{
return nums2[index2+k-1];
}
if(index2==m)
{
return nums1[index1+k-1];
}
if(k==1)
{
return min(nums1[index1],nums2[index2]);
}
int newindex1=min(index1+k/2-1,n-1);
int newindex2=min(index2+k/2-1,n-1);
if(nums1[newindex1]<=nums2[newindex2])
{
k-=newindex1-index1+1;
index1=newindex1+1;
}else{
k-=newindex2-index2+1;
index2=newindex2+1;
}
}
}
};
C++ 解法, 执行用时: 31ms, 内存消耗: 3376KB, 提交时间: 2022-04-23
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums1 int整型vector
* @param nums2 int整型vector
* @return double浮点型
*/
int findKth(vector<int>::const_iterator A, int m, vector<int>::const_iterator B, int n, int k) {
if (m > n) return findKth(B, n, A, m, k);
if (m==0) return B[k-1];
if (k==1) return min(A[0], B[0]);
int ia = min(m, k/2), ib = k - ia;
if (A[ia-1] < B[ib-1]) {
return findKth(A + ia, m - ia, B, n, k - ia);
} else if (A[ia-1] > B[ib-1]) {
return findKth(A, m, B + ib, n - ib, k - ib);
} else {
return A[ia-1];
}
}
double Median(vector<int>& nums1, vector<int>& nums2) {
// write code here
int m = nums1.size();
int n = nums2.size();
int total = m + n;
if (total & 1) {
return findKth(nums1.begin(), m, nums2.begin(), n, total/2+1);
} else {
return (findKth(nums1.begin(), m, nums2.begin(), n, total/2+1) + findKth(nums1.begin(), m, nums2.begin(), n, total/2)) * 0.5;
}
}
};
C++ 解法, 执行用时: 32ms, 内存消耗: 3392KB, 提交时间: 2022-08-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums1 int整型vector
* @param nums2 int整型vector
* @return double浮点型
*/
double Median(vector<int>& nums1, vector<int>& nums2) {
// write code here
int n = nums1.size() + nums2.size();
if(n % 2){
return getKmedian(nums1, nums2, (n + 1) / 2);
}else{
return (getKmedian(nums1, nums2, n / 2 + 1) + getKmedian(nums1, nums2, n / 2)) / 2.0;
}
}
double getKmedian(vector<int>& nums1, vector<int>& nums2, int k){
int m = nums1.size();
int n = nums2.size();
int idx1 = 0;
int idx2 = 0;
while(k){
// cout<<k<<idx1<<idx2<<endl;
//特殊情况1
if(k==1) return min(nums1[idx1],nums2[idx2]);
//特殊情况2，其中一个数组被全部舍弃
if(idx1==m) return nums2[idx2+k-1];
if(idx2==n) return nums1[idx1+k-1];
//注意这里不能超过m-1 n-1
int idxNew1 = min(m-1,idx1+k/2-1); //若取idx1+k/2-1，[idx1,idxNew]共有k/2个数，即每次打算减k/2个数
int idxNew2 = min(n-1,idx2+k/2-1);
if(nums1[idxNew1]<=nums2[idxNew2]){
k -= idxNew1-idx1+1; //去除[idx,idxNew1]的全部元素
idx1 = idxNew1+1;
}
else{
k -= idxNew2-idx2+1;
idx2 = idxNew2+1;
}
}
return 0;
}
};