当前位置 博文首页 > Inmaturity_7的博客：算法练习贴--70--寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
（题目来源：力扣（LeetCode））
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000
提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
//新建一个数组，数组长度等于这两个数组大小总长
int*newnums=(int*)malloc(sizeof(int)*(nums1Size+nums2Size));
int i=0;//nums1Size数组指针
int j=0;//nums2Size数组指针
int index=0;
while(i<=nums1Size-1&&j<=nums2Size-1){//将两个子数组数据排序并赋值进总数组
if(nums2[j]<nums1[i])
{
newnums[index++]=nums2[j++];
}
else
{
newnums[index++]=nums1[i++];
}
}
while(i<=nums1Size-1){//将数组1剩余数据继续赋值
newnums[index++]=nums1[i++];
}
while(j<=nums2Size-1){//将数组2剩余数据继续赋值
newnums[index++]=nums2[j++];
}
if((nums1Size+nums2Size)%2==0){//将总数组中的中位数返回
return ((double)newnums[(nums1Size+nums2Size)/2]+(double)newnums[(nums1Size+nums2Size)/2-1])/2;
}else{
return (double)newnums[(nums1Size+nums2Size)/2];
}
}
#include<stdio.h>
//寻找两个正序数组的中位数
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
//当一个数组为空，直接返回另一个数组的中位数
if(nums1Size==0){
if(nums2Size%2==0){
return (double)(nums2[nums2Size/2]+nums2[nums2Size/2-1])/2;
}else{
return (double)nums2[nums2Size/2];
}
}
if(nums2Size==0){
if(nums1Size%2==0){
return (double)(nums1[nums1Size/2]+nums1[nums1Size/2-1])/2;
}else{
return (double)nums1[nums1Size/2];
}
}
int sum=nums1Size+nums2Size;//两个数组总长
int count=(sum-1)/2;//需要移除的数据个数
int i=0,j=0;//双指针,i是nums1的，j是nums2的
while(count>0){
if(nums1[i]>nums2[j]){//移除数据较小者
j++;
}else{
i++;
}
count--;
//当一个数组为空，则计算并返回中位数
//说明一个数组的最小值大于另一个数组的最大值（我们称这种为不交融）
if(i>nums1Size-1){
int index=sum/2-nums1Size-1;
if(sum%2==0){
return (double)(nums2[index]+nums2[index+1])/2;
}else{
return (double)nums2[index+1];
}
}
if(j>nums2Size-1){
int index=sum/2-nums2Size-1;
if(sum%2==0){
return (double)(nums1[index]+nums1[index+1])/2;
}else{
return (double)nums1[index+1];
}
}
}
//当两个数组数据交融，如果是奇数个数据则返回i,j对应数组中最小的那个值
//但是偶数个数据时我们需要注意：有可能未取到两个中位数
if(sum%2==0){
//获取两个值
int num1=nums1[i];
int num2=nums2[j];
if(num1<num2&&i<nums1Size-1){
//判断第二个值是否为中位数
num2=nums1[i+1]<num2?nums1[i+1]:num2;
}else if(num1>num2&&j<nums2Size-1){
//判断第一个值是否为中位数
num1=nums2[j+1]<num1?nums2[j+1]:num1;
}
return (double)(num1+num2)/2;
}else{
return (double)nums1[i]>nums2[j]?nums2[j]:nums1[i];
}
}
int main(){
int nums1[]={2,2,2};
int nums2[]={2,2,2,2};
printf("中位数：%lf",findMedianSortedArrays(nums1,3,nums2,4));
}
#include<stdio.h>
int getKthElement(int* nums1,int nums1Size,int* nums2,int nums2Size, int k) {
int index1 = 0, index2 = 0;
while (true) {
// 边界情况
if (index1 == nums1Size) {
return nums2[index2 + k - 1];
}
if (index2 == nums2Size) {
return nums1[index1 + k - 1];
}
//将中位数左边的数全部删除了
if (k == 1) {
return nums1[index1]>nums2[index2]?nums2[index2]:nums1[index1];
}
// 正常情况：获取下一个中位线左边数据的下标
int newIndex1 =(index1 + k / 2 - 1)>(nums1Size - 1)?nums1Size - 1:(index1 + k / 2 - 1);
int newIndex2 =(index2 + k / 2 - 1)>(nums2Size - 1)?nums2Size - 1:(index2 + k / 2 - 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(int* nums1, int nums1Size, int* nums2, int nums2Size){
int totalLength = nums1Size + nums2Size;
if (totalLength % 2 == 1) {
return getKthElement(nums1,nums1Size, nums2, nums2Size,(totalLength + 1) / 2);//两个数组的总数为奇数
}
else {
return (getKthElement(nums1, nums1Size,nums2, nums2Size,totalLength / 2) + getKthElement(nums1,nums1Size,nums2,nums2Size, totalLength / 2 + 1)) / 2.0;//两个数组的总数为偶数
}
}
