如果这个问题不属于这里，我很抱歉，我的问题不在于代码，而在于算法，所以也许它更适合另一个网站，但 stackoverflow 的好人从未让我失望。
这是问题：
给定 2 个排序数组A，并且B它们具有相同数量的元素，假设n，并且它们不共享元素，并且没有元素在同一个数组中出现两次，以对数时间复杂度找到数组并集的中位数.
非常重要的说明：如果n是奇数，则中位数是中间元素。但如果n是偶数，则中位数不是中间元素的平均值。它被定义为中间元素的最小值。
解决方案：这个想法很简单。由于它们是排序的，我们可以找到(call ) 的中位数和 (call )A的中位数。如果那么我们知道并集的中位数是 小于的元素或大于的元素，如果 则相反。所以我们扔掉多余的元素并做同样的过程，直到和足够小，比如说每个有 2 个元素，然后我们只需要找到这 4 个数字之间的中位数。4 个数字的中位数将是第二个最小值，因为 4 是偶数，即.med1Bmed2O(1)med1>med2Amed1Bmed2med2>med1ABO(1)
这是我的代码
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
int *scan_array(int* array_length);
int second_min_four_numbers(int a,int b,int c,int d);
int first_question(int *arr1,int *arr2,int left1,int right1,int left2,int right2);
void main()
{
int *arr1,*arr2,length_arr1=0,length_arr2=0;
printf("For the first sorted array:\n");
arr1=scan_array(&length_arr1);
printf("\nFor the second sorted array, enter %d numbers:\n",length_arr1);
arr2=scan_array(&length_arr2);
if(length_arr1==1) //edge case, arrays are length one. return the min
{
if(arr1[0] > arr2[0])
printf("The Median is %d",arr2[0]);
else
printf("The Median is %d",arr1[0]);
}
else
printf("The Median is %d",first_question(arr1,arr2,0,length_arr1-1,0,length_arr2-1));
getch();
}
int *scan_array(int* array_length) //nothing fancy. just scan the arrays.
{
int* temp,temp_length,array_element,i=0,*real_array;
temp=(int*)malloc(50*sizeof(int));
printf("Enter positive numbers. To stop enter negative or zero.\nDon't enter more than 50 numbers\n");
scanf("%d",&array_element);
while(array_element>0)
{
(*array_length)++;
temp[i]=array_element;
i++;
scanf("%d",&array_element);
}
real_array=(int*)malloc((*array_length)*sizeof(int));
for(i=0;i<*array_length;i++)
real_array[i]=temp[i];
free(temp);
return real_array;
}
int first_question(int *arr1,int *arr2,int left1,int right1,int left2,int right2)
{
int med1,med2;
if(right1-left1+right2-left2 == 2) //we are done. reached 4 elements. we will always be here for arrays larger than 1 element each
return second_min_four_numbers(arr1[left1],arr1[right1],arr2[left2],arr2[right2]);
med1=arr1[(left1+right1)/2]; //not done. find the medians in O(1).
med2=arr2[(left2+right2)/2];
if(med1 < med2)//the median of the union is somewhere between them
return first_question(arr1,arr2,(left1+right1)/2,right1,left2,(left2+right2)/2);
else
return first_question(arr1,arr2,left1,(left1+right1)/2,(left2+right2)/2,right2);
}
int second_min_four_numbers(int a,int b,int c,int d) //find second min between four numbers
{
int min=0,second_min=0; //very crude, and inefficient but simple to understand and still O(1)
min = a;
if(min > b)
min = b;
if(min > c)
min = c;
if(min > d)
min = d;
if(a == min)
{
second_min=b;
if(second_min > c)
second_min = c;
if(second_min > d)
second_min = d;
return second_min;
}
if(b == min)
{
second_min=a;
if(second_min > c)
second_min=c;
if(second_min > d)
second_min = d;
return second_min;
}
if(c == min)
{
second_min=a;
if(second_min > b)
second_min = b;
if(second_min > d)
second_min = d;
return second_min;
}
if(d == min)
{
second_min=a;
if(second_min > b)
second_min=b;
if(second_min > c)
second_min=c;
return second_min;
}
}
它按预期工作并编译。正如我所说，问题不在于我的代码，而在于算法。让我们看一个演示该问题的示例：
假设我们的输入是A=[1,3,5]和B=[2,4,6]。然后med1=3和med2=4。扔掉多余的元素，现在我们有了A=[3,5]和B=[2,4]。现在我们总共只有 4 个元素，数据足够小，所以只需找到这 4 个数字的中位数即可[3,5,2,4]。中位数是3，这也是 和 的并集的中位数的正确结果A，B所以结果是正确的。
现在让我们假设我们的输入是A=[1,3,5,7]和B=[2,4,6,8]。med1=3和med2=4。扔掉多余的元素得到A=[3,5,7]和B=[2,4]。现在med1=5和med2=2。再次丢弃冗余得到A=[3,5]和B=[2,4]。现在我们的数据足够小，找到其中的中位数[3,5,2,4]将再次给我们3。但这个结果是不正确的。3不是 和 的并集的中A位数B。正确的结果是4.
我们如何解决这个问题？