最大増加差

Question

ベクター内の数字の間の最大距離または差を見つける必要があります。たとえば、ベクトル[10, 5, 20, 45, 5, 5, 7]の最初のパスでは、10と45の差が最大であるように見えます。しかし、2回目の反復では5と45の差が大きいので、アルゴリズムによって選択する必要があります。

私は解決策を持っていますが、それはO（n^2）です。私の人生では、計算量がより少ない解決策があるかどうかはわかりません。

public void maxDistance(int inputArray[]) { 
    int trueMaxValue = 0, trueMinIndex = 0, trueMaxIndex = 0, tempMaxValue; 

    for (int i = 0; i < inputArray.length - 1; ++i) { 
     for (int j = i + 1; j < inputArray.length; ++j) { 
      tempMaxValue = inputArray[j] - inputArray[i]; 
      if (tempMaxValue > trueMaxValue) { 
       trueMaxValue = tempMaxValue; 
       trueMinIndex = i; 
       trueMaxIndex = j; 
      } 
     } 
    } 
} 

また、配列内のどの2つの数値がmaxで使用されたかを知る必要があります。あなたは助けてもらえますか？私はそれについて考え続けるべきか、O（n^2）があなたができる最良のものなのかどうか分かりません。

Answer 1

あなたはO（n）Stephanyで実行できます。現在の最良の解決策が何であるかを覚えておくために、いくつかの変数を追加する必要があります。あなたは次の操作を行うことができますあなたの現在の命名規則を使用して：

public void maxDistance(int inputArray[]) { 
     int currentMin = inputArray[0],  currentMinIndex = 0; 
     int trueMaxValue = 0, trueMinIndex = 0, trueMaxIndex = 0; 
     int tempMaxValue; 

     int i = 1; 
     while (i < inputArray.length) { 
      tempMaxValue = inputArray[i] - inputArray[currentMinIndex]; 
      if (tempMaxValue > trueMaxValue) { 
       trueMaxValue = tempMaxValue; 
       trueMinIndex = currentMinIndex; 
       trueMaxIndex = i; 
      } 

      if (inputArray[i] < currentMin) { 
       currentMinIndex = i; 
       currentMin = inputArray[i]; 
      } 

      ++i; 
     } 

Answer 2

たぶん私は何か足りないのです：配列

を繰り返す

• を最小のエントリ
• を決定する最大のエントリ
• を決定デルタ（最大 - 最小）を計算

を

これはすべて1回の繰り返しで実行できます。これは5と45を見つけ、40の差を与えるでしょう。

Answer 3

これは、線形時間で行うことができます。これまで を見最小の数を追跡し、

1. 反復配列オーバー：ここ

   は概要です。

2. これまでに見た最小の数字と現在の数字の差を計算し、最大の差異を記録します。

Voilà。

Answer 4

あなたは間違いなく、より良いオプションを持っています。なぜ入れ子にされたループが必要なのかわからない。インデックスを含めるように編集しますが、なぜ配列が重複している可能性があると考えられるのかはわかりません。

int[] inputArray = new int[] {10,5,20,5,5,46,7}; 
int max = 0; 
int min = Integer.MAX_VALUE; 
for (int i = 0; i < inputArray.length; i++) { 
    max = inputArray[i] > max ? inputArray[i] : max; 
    min = inputArray[i] < min ? inputArray[i] : min; 
} 
int delta = max - min; 

私はインデックスを含めるように編集しますが、それは重複した番号を持つことができ、あなたの配列を考慮した場合のシナリオで便利ですなぜ私はよく分かりません。

int[] inputArray = new int[] {10,5,20,5,5,46,7}; 
int max = 0; 
int min = Integer.MAX_VALUE; 
int maxIndex = -1; 
int minIndex = -1; 
for (int i = 0; i < inputArray.length; i++) { 
    if (inputArray[i] > max) { 
     max = inputArray[i]; 
     maxIndex = i; 
    } 
    if (inputArray[i] < min) { 
     min = inputArray[i]; 
     minIndex = i; 
    } 
} 
int delta = max - min;