最大で1.5nの比較で高/低の数を見つけるアルゴリズム

Question

私はこの宿題に関する質問を今少し考えてきました。サイズnの配列が与えられた場合、高低の値を最大1.5nの比較で見つけるアルゴリズムを設計します。

私の最初の試みは、私の問題は、ループの各反復は、三つの可能性の一つを有するある

int high=0 
int low= Number.MaxValue //problem statement is unclear on what type of number to use 
Number numList[0 . . n] //number array, assuming unsorted 

for (i=0, i < n, i++) { 
    if (numList[i] > high) 
    high = numList[i] 

    else if (numList[i] < low) 
    low = numList[i] 

} 

た：

• 低い値が発見された - 1つの比較が
• 高い値が検出された作られたが - 2比較を行った
• どちらも見つかりませんでした - 2比較が行われました

したがって、配列トラバーサル全体に対して、最大2n回の比較が可能です。これは、1.5n回の比較の問題の最大要件とはまったく異なります。

Answer 1

数字のペアから始め、ローカルminとmax（n/2比較）を見つけます。次に、n/2ローカル・マックス（n/2比較）からグローバル・マックスを、同様にローカル・ミニ（n/2比較）からグローバルminを検索します。合計比較：3 * n/2！

For i in 0 to n/2: #n/2 comparisons 
    if x[2*i]>x[2*i+1]: 
     swap(x,2*i,2*i+1) 

global_min = min(x[0], x[2], ...) # n/2 comparisons 
global_max = max(x[1], x[3], ...) # n/2 comparisons 

上記の解決策は配列を変更することに注意してください。代替ソリューション：

Initialize min and max 
For i = 0 to n/2: 
    if x[2*i]<x[2*i+1]: 
     if x[2*i]< min: 
      min = x[2*i] 
     if x[2*i+1]> max: 
      max = x[2*i+1] 
    else: 
     if x[2*i+1]< min: 
      min = x[2*i+1] 
     if x[2*i]> max: 
      max = x[2*i] 

Answer 2

これはElKaminaと同じ答えですが、私はすでに擬似コードを書き始めていたように私は、私はそれを終了し、投稿しようと思いました。

対の値（n/2比較）を比較して、高い値の配列と低い値の配列を取得することです。それらの配列のそれぞれについて、我々は再び値の対（2 * n/2の比較）を比較して最高値と最低値を得る。

int[] highNumList; 
int[] lowNumList; 

for (i = 0, i < n, i+=2) 
{ 
    a = numList[i]; 
    b = numList[i+1]; 
    if (a > b) 
    { 
     highNumList.Add(a); 
     lowNumlist.Add(b); 
    } 
    else 
    { 
     highNumlist.Add(b); 
     lowNumList.Add(a); 
    } 
} 

int high = highNumList[0]; 
int low = lowNumList[0]; 

for (i = 0, i < n/2, i+=2) 
{ 
    if (highNumList[i] < highNumList[i+1]) 
     high = highNumList[i+1] 
    if (lowNumList[i] > lowNumList[i+1]) 
     low = lowNumList[i+1] 
} 

このコードはnもされていないか、初期配列が空であることを考慮していない：

n/2 + 2*n/2 = 1.5n comparisons 

はここで擬似コードです。

Answer 3

これは私がインタビューの中で持っていた質問であり、インタビュアーからの小さなヒントで答えが見つかりました。「どのように2つの数字を比較しますか？ （それは本当に助けになった）。ここで

は説明です：

は、私は（あなたが簡単にnでそれを置き換えることができますが、nが偶数である場合、それは例えば、より良い仕事）100個の番号を持っているとしましょう。私は、2つの数字からなる50のリストに分割しています。それぞれのカップルについて、私は1つの比較を行い、これまでに50回の比較を行っています。次に、最小値（49比較値）と最大値の最大値（49比較値49 + 49 + 50 = 148の比較をする必要があります）。もう終わった ！

備考：我々は（擬似コードで）次のように進行最小見つける：

n=myList.size(); 
    min=myList[0]; 
    for (int i(1);i<n-1;i++) 
    { 
    if (min>myList[i]) min=myList[i]; 
    } 
    return min; 

を我々は（N-1）の比較にそれを見つけます。コードは最大限にほぼ同じです。

Answer 4

私はこれが既に答えられていることを知っていますが、誰かがこれについて考える別の方法を探している場合に備えてです。この回答はLester'sに似ていますが、破損することなくnの奇数の値を扱うことができ、最大でも1.5nの比較を行います。秘密はモジュラスにある。 ;）

最後の値を正しいサブ配列に配置するための副作用として、givenListの2番目の要素が比較され、2回配置されます。しかし、元の配列は変更されておらず、セットの高低にのみ関心があるため、実際には違いはありません。この種の問題で

Initialize lowArray and highArray 
Initialize subArrayCounter to 0 

For i = 0; i < n; i+=2 
    X = givenList[i]; 
    Y = givenList[(i+1)%n]; 
    If(x < y) 
     lowArray[subArrayCounter] = x; 
     highArray[subArrayCounter] = y; 
     subArrayCounter++; 
    else 
     lowArray[subArrayCounter] = y; 
     highArray[subArrayCounter] = x; 
     subArrayCounter++; 

Initialize low to lowArray[0]; 
Initialize high to highArray[0]; 

For i = 1; i < lowArray.length; i++ 
    If(lowArray[i] < low) 
     Low = lowArray[i]; 

For i = 1; i < highArray.length; i++ 
    If(highArray[i] > high) 
     High = highArray[i]