k個の配列が各配列の少なくとも1つの要素の最小範囲を含むことを求めます(字の娘の中で、忘れます)
k個の秩序ある配列があります.最小の数値範囲を見つけてください.このk個の秩序配列において、各配列には少なくとも1つの数字がこの範囲内にあるようにする.
例:
1: 4, 10, 15, 24, 26
2: 0, 9, 12, 20
3: 5, 18, 22, 30
得られた最小範囲は[20,24]であり、ここで、20は2、22は3、24は1である.
これは字を待つ娘の中の1つの面接問題で、個人の経験から見ると一般的な秩序配列の問題はすべて人に半分の検索があって解決することを連想させて、秩序配列が複数の時、一般的に集計並べ替えの思想を連想して、それではこの問題は例外ではありません.
以下は待機中の親友の分析から引用する.
では、このテーマはどの方法を選んで試し続けますか?では、解決すべき問題をもう一度分析しましょう.最小の範囲を見つけます.各秩序配列には、少なくとも1つの要素がこの範囲にあります.このような範囲を見つけるのは難しくありませんが、どのようにして最小の範囲を確定しますか?最終的に得られる最小の範囲は、少なくとも3つの要素を含み、すべての配列全体のソートにおいて隣接している.最小範囲を[a,b,c],adはaが存在する配列から来ているので、より短い範囲c-d があるべきである.
dはcが存在する配列から来ているので、より短い範囲d-a があるべきである.
dはbが存在する配列から来ており,範囲の大きさは不変であり,dを考慮してもbを考慮してもよい.影響はありません.
以上の解析から,最終的な並べ替えにおいて,代替範囲として隣接し,異なる秩序配列からの要素を考慮するだけでよいことを導いた.では、近い、異なる秩序配列からの要素だけを考慮するにはどうすればいいのでしょうか.ここでは集計ソートの考え方を用いた.原題の例を例にとると、3つのポインタ指、p 1、p 2、p 3があり、それぞれ3つの配列の最初の要素を指すと仮定する.
ステップ
ポインタ現在値
最大値
最小値
min_range_value
ポインタの移動
1
4,0,5
5
0
5
p2
2
4,9,5
9
4
5
p1
3
10,9,5
10
5
5
p3
4
10,9,18
18
9
9
p2
5
10,12,18
18
10
8
p1
6
15,12,18
18
12
6
p2
7
15,20,18
20
15
5
p1
8
24,20,18
24
18
6
p3
9
24,20,22
24
20
4
p2
end
最後に,2番目の配列にはもう要素が遍歴できないためである.最終的に最小min_を得るrange_valueは4で、テーマの例の答えです.
以上の方法では,集計ソートの考え方により,毎回k個の異なる配列からの要素が比較され,最大値,最小値が得られることを確保した.すべての配列の数字を含む範囲が得られます.
この問題の有名な変種は,すべてのクエリ語を含む最小の要約をウェブページから生成することである.Googleに会ったことがあるなら、この問題を聞いたことがあるはずです.
個人的な理解:
実は集計の思想を利用して、3つの配列あるいはもっと多くの配列を集計して並べ替えて、最小の要素に並んで前に移動して、最大の最小の要素の間の間隔を計算して、このように1つの配列が尽きた時、記録の最小の間隔は求めます.
例:
1: 4, 10, 15, 24, 26
2: 0, 9, 12, 20
3: 5, 18, 22, 30
得られた最小範囲は[20,24]であり、ここで、20は2、22は3、24は1である.
これは字を待つ娘の中の1つの面接問題で、個人の経験から見ると一般的な秩序配列の問題はすべて人に半分の検索があって解決することを連想させて、秩序配列が複数の時、一般的に集計並べ替えの思想を連想して、それではこの問題は例外ではありません.
以下は待機中の親友の分析から引用する.
では、このテーマはどの方法を選んで試し続けますか?では、解決すべき問題をもう一度分析しましょう.最小の範囲を見つけます.各秩序配列には、少なくとも1つの要素がこの範囲にあります.このような範囲を見つけるのは難しくありませんが、どのようにして最小の範囲を確定しますか?最終的に得られる最小の範囲は、少なくとも3つの要素を含み、すべての配列全体のソートにおいて隣接している.最小範囲を[a,b,c],a
dはcが存在する配列から来ているので、より短い範囲d-a があるべきである.
dはbが存在する配列から来ており,範囲の大きさは不変であり,dを考慮してもbを考慮してもよい.影響はありません.
以上の解析から,最終的な並べ替えにおいて,代替範囲として隣接し,異なる秩序配列からの要素を考慮するだけでよいことを導いた.では、近い、異なる秩序配列からの要素だけを考慮するにはどうすればいいのでしょうか.ここでは集計ソートの考え方を用いた.原題の例を例にとると、3つのポインタ指、p 1、p 2、p 3があり、それぞれ3つの配列の最初の要素を指すと仮定する.
ステップ
ポインタ現在値
最大値
最小値
min_range_value
ポインタの移動
1
4,0,5
5
0
5
p2
2
4,9,5
9
4
5
p1
3
10,9,5
10
5
5
p3
4
10,9,18
18
9
9
p2
5
10,12,18
18
10
8
p1
6
15,12,18
18
12
6
p2
7
15,20,18
20
15
5
p1
8
24,20,18
24
18
6
p3
9
24,20,22
24
20
4
p2
end
最後に,2番目の配列にはもう要素が遍歴できないためである.最終的に最小min_を得るrange_valueは4で、テーマの例の答えです.
以上の方法では,集計ソートの考え方により,毎回k個の異なる配列からの要素が比較され,最大値,最小値が得られることを確保した.すべての配列の数字を含む範囲が得られます.
この問題の有名な変種は,すべてのクエリ語を含む最小の要約をウェブページから生成することである.Googleに会ったことがあるなら、この問題を聞いたことがあるはずです.
個人的な理解:
実は集計の思想を利用して、3つの配列あるいはもっと多くの配列を集計して並べ替えて、最小の要素に並んで前に移動して、最大の最小の要素の間の間隔を計算して、このように1つの配列が尽きた時、記録の最小の間隔は求めます.
/*************************************************************************
> File Name: mindiff.c
> Author: desionwang
> Mail: [email protected]
> Created Time: Wed 23 Oct 2013 02:57:44 PM CST
************************************************************************/
#include<stdio.h>
int mindiff(int a[], int size_a, int b[], int size_b, int c[], int size_c){
int i = 0, j = 0 ,k = 0;
int minnum;
int mindiff = 65535;
if(a == NULL || b == NULL || c == NULL){
return -1;
}
if(size_a <= 0 || size_b <= 0 || size_c <= 0){
return -1;
}
int max, min, diff;
int index;
while(i < size_a && j < size_b && k < size_c){
printf("a:%d\tb:%d\tc:%d
", a[i], b[j], c[k]);
if(a[i] >= b[j]){
if(a[i] >= c[k]){
max = a[i];
}else{
max = c[k];
}
if(b[j] <= c[k]){
min = b[j];
index = j;
j++;
}else{
min = c[k];
index = k;
k++;
}
}else{
if(b[j] >= c[k]){
max = b[j];
}else{
max = c[k];
}
if(a[i] <= c[k]){
min = a[i];
index = k;
i++;
}else{
min = c[k];
index = i;
k++;
}
}
printf("max:%d\tmin:%d
", max, min);
//printf("a:%d\tb:%d\tc:%d
", a[i], b[j], c[k]);
diff = max - min;
if(diff < mindiff){
mindiff = diff;
}
}
//printf("a:%d\tb:%d\tc:%d
", a[i], b[j--], c[k]);
printf("mindiff:%d
", mindiff);
return mindiff;
}
int main(){
int a[5] = {4, 10, 15, 24, 26};
int b[] = {0, 9, 12, 20};
int c[] = {5, 18, 22, 30};
mindiff(a, 5, b, 4, c , 4);
}