递归完成后要做什么

2018-06-30 01:03:13

我很抱歉如果这个问题不属于这里，我的问题不在于代码，它是与算法，所以也许它更适合另一个网站，但是stackoverflow的好人从不让我失望。

这是一个问题：

给定2个排序的数组A和B ，使它们具有相同数量的元素，让我们说n ，并且使得它们不共享元素，并且没有元素在相同数组中出现两次，找到数组联合的中位数对数时间复杂度。

非常重要的注意事项：如果n是奇数，则中位数是中间元素。但是如果n是偶数，那么中值不是中间元素的平均值。它被定义为中间元素的最小值。

解决方案 ：这个想法很简单。因为它们是排序的，我们可以在O(1)中找到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 numbersn");
    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 。

我们如何解决这个问题？

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

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

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

为了继续这个例子，假设B=[20,25,26,27] 。从B提出的候选人是25.A的候选人较低，所以我们评估19.列表A有3个值低于19，高1。列表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是这两个列表中唯一剩下的候选人，因此是答案。

让我提出一个不同的概念化这个问题的方法。假设每个数组中有4个元素。考虑这个网格：

a1 a2 a3 a4
b1 b2 b3 b4

我们正在寻找通过安排的中心的一条线，这保证线的左边的条目数和右边的条目的数目是相等的。还要注意的是，有两种不同的水平线作为划分条目的可能方式（小于或大于小于）。所以我们需要考虑的行数是5，在这种情况下，总体上n + 1。现在，通过二进制搜索应该做的伎俩。

链接地址: http://www.djcxy.com/p/83829.html

上一篇: what to do after recursion ends

下一篇: Find a median of N^2 numbers having memory for N of them