c - 排序数组 union 的中位数 - 递归结束后做什么

Question

如果这个问题不属于这里，我深表歉意，我的问题不在于代码，而在于算法，所以也许它更适合另一个网站，但 stackoverflow 的好人永远不会让我失望。

这里是问题:

给定 2 个排序数组 A 和 B，它们具有相同数量的元素，假设 n，并且它们确实如此不共享元素，并且没有元素在同一个数组中出现两次，求对数时间复杂度的数组并集的中位数。

非常重要的提示:如果n是奇数，那么中位数就是中间的元素。但如果 n 是偶数，则中位数不是中间元素的平均值。它被定义为中间元素的最小值。

解决方案:思路很简单。由于它们已排序，我们可以找到 A 的中位数(称为 med1)和 B 的中位数(称为 med2) 在 O(1) 中。如果 med1>med2 那么我们知道并集的中位数是 A 的一个元素，它小于 med1 或者 的一个元素>B 大于med2，如果med2>med1 则相反。所以我们扔掉多余的元素并做同样的过程，直到 A 和 B 足够小，比如每个有 2 个元素，然后我们只需要找到中位数在这4个数字之间。 4 个数字的中位数将是第二个最小值，因为 4 是偶数，这将是 O(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。

我们如何解决这个问题？

Answer 1

算法需要对中位数进行二分查找，即提出一个可能的中位数值。如果该值太低，则在下一次迭代中选择更高的值。如果太高，则选择较低的值。

在每次迭代中，我们从 A 中选择一个候选者，并从 B 中选择一个候选者。较小的候选者被提议作为中值，并进行评估。如果建议的中位数太小，则可以从考虑中删除 A 和 B 中所有较小的值。同样，如果建议的中位数太大，则可以忽略 A 和 B 中较大的值。

例如，给定A=[1,2,7,19,22]来自 A 的候选人将是 7。假设 B 提出了更大的候选人，因此选择 7 作为可能的中位数。如果 7 太低，那么我们可以消除所有元素 <= 7在 A 和 B 中都是可能的候选人。所以 A 变成 A=[1,2,7,{19,22}]其中大括号中的元素是中位数的剩余可能候选者。重复该过程，但这次来自 A 的候选人将是 19 岁。

继续这个例子，假设B=[20,25,26,27] . B 建议的候选人是 25。A 的候选人较低，因此我们评估 19。列表 A 有 3 个值低于 19，有 1 个值高于 19。列表 B 的值高 4 个。总共 3 个低，5 个高。结论:19 太低，所以尽可能排除所有数字 <= 19 的候选人。两次通过后我们有

A=[1,2,7,19,{22}]  B=[{20,25,26,27}]

A 的候选人是 22，B 的候选人是 25，建议 22 作为中位数。 22 太高了，所以数字 >= 22 可以忽略，我们有

A=[1,2,7,19,{},22]  // 19 was too low and 22 was too high, so no candidates are left in A
B=[{20},25,26,27]   // 22 was too high, so the only remaining candidate in B is 20

20 是两个列表中唯一剩下的候选者，因此是答案。