この質問がここに属していない場合は申し訳ありません。私の問題はコードではなく、アルゴリズムにあるため、別の Web サイトに適している可能性がありますが、stackoverflow の善良な人々は決して私を失望させませんでした。
質問は次のとおりです。
2 つの並べ替えられた配列が与えられA、Bそれらが同じ数の要素を持ち、それらがn要素を共有せず、同じ配列に要素が 2 回出現しないように、対数時間の複雑さで配列の和集合の中央値を見つけます。 .
非常に重要な注意:nが奇数の場合、中央値は中央の要素です。しかし、nが偶数の場合、中央値は中間要素の平均ではありません。中間要素の最小値として定義されます。
解決策: アイデアは非常に単純です。それらはソートされているため、 (と呼ばれる) の中央値と (と呼ばれる)のA中央値を で見つけることができます。の場合、和集合の中央値は の要素であることがわかります より小さいか、または の要素は よりも大きく、その逆の場合. したがって、冗長な要素を捨てて、 と がそれぞれ 2 つの要素で十分に小さくなるまで、同じプロセスを実行します。その後、これら 4 つの数値の間の中央値を見つけるだけで済みます。4 は偶数であるため、4 の数値の中央値は 2 番目の最小値になります。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の結合の中央値の正しい結果でもあるため、結果は正しいです。AB
A=[1,3,5,7]ここで、入力がと であると仮定しましょうB=[2,4,6,8]。med1=3とmed2=4。冗長な要素を捨てて getA=[3,5,7]とを取得しB=[2,4]ます。今med1=5とmed2=2。ここでも冗長性を捨てて getA=[3,5]およびを取得しB=[2,4]ます。これで、データは十分に小さくなりました。その中央値を求めると、[3,5,2,4]再び が得られ3ます。しかし、その結果は正しくありません。はと3の結合の中央値ではありません。正しい結果は になります。AB4
どうすればこの問題を解決できますか?