Медиана объединения отсортированных массивов - что делать после окончания рекурсии

Question

Я извиняюсь, если этот вопрос здесь не относится, моя проблема не в коде, а в алгоритме, так что, возможно, он лучше подходит для другого сайта, но хорошие люди из stackru никогда не подводят меня.

Вот вопрос:

Дано 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

Позвольте мне предложить другой способ осмысления этой проблемы. Предположим, есть 4 элемента в каждом массиве. Рассмотрим эту сетку:

a1 a2 a3 a4
b1 b2 b3 b4

Мы ищем линию через центр соглашения, которая гарантирует, что количество записей слева от строки и количество записей справа от строки равны. Также обратите внимание, что есть две разные горизонтальные линии в качестве возможного способа разделения записей (меньше вверху или меньше внизу). Таким образом, количество строк, которое нам нужно рассмотреть, равно 5 в данном случае, n+1 в общем случае. Теперь бинарный поиск по строкам должен помочь.

Answer 2

Алгоритм должен реализовывать двоичный поиск медианы, т.е. предлагать возможное значение медианы. Если это значение слишком мало, выберите более высокое значение на следующей итерации. Если слишком высокое, выберите меньшее значение.

На каждой итерации мы выбираем кандидата из A и выбираем кандидата из B. Меньший кандидат предлагается в качестве медианы и оценивается. Если предложенная медиана слишком мала, то все меньшие значения из A и B могут быть сняты с рассмотрения. Аналогичным образом, если предложенная медиана слишком велика, большие значения из A и B можно игнорировать.

Например, учитывая A=[1,2,7,19,22] кандидатом от A будет 7. Предположим, что B предлагает более крупного кандидата, поэтому 7 выбирается в качестве возможной медианы. Если 7 слишком мало, то мы можем удалить все элементы <= 7 в обоих А и В в качестве возможных кандидатов. Так А становится A=[1,2,7,{19,22}] где элементы в фигурных скобках - остальные возможные кандидаты на медиану. Процесс повторяется, но на этот раз кандидату от А будет 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}]

Кандидат А - 22, В - 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 - единственный оставшийся кандидат в любом списке, и поэтому является ответом.