Java配列の最大値のインデックスを取得する

Question

サイズが1000の配列があります。5つの最大要素のインデックス（インデックス）はどのようにして見つけることができますか？

セットアップコードと私の試みとの例を以下に表示されます。

Random rand = new Random(); 
int[] myArray = new int[1000]; 
int[] maxIndices = new int[5]; 
int[] maxValues = new int[5]; 

for (int i = 0; i < myArray.length; i++) { 
    myArray[i] = rand.nextInt(); 
} 

for (int i = 0; i < 5; i++) { 
    maxIndices[i] = i; 
    maxValues[i] = myArray[i]; 
} 

for (int i = 0; i < maxIndices.length; i++) { 
    for (int j = 0; j < myArray.length; j++) { 
    if (myArray[j] > maxValues[i]) { 
     maxIndices[i] = j; 
     maxValues[i] = myArray[j]; 
    } 
    } 
} 

for (int i = 0; i < maxIndices.length; i++) { 
    System.out.println("Index: " + maxIndices[i]); 
} 

を私はこの問題は、それは常に、すべての最大の要素への最高の最大値を代入していることを知っています。 myArrayの値と指標を保存する必要があるため、これをどのように修正するかはわかりません。

私はインデックスを保持する必要があるので、並べ替えはオプションではないと思います。実際、それは私が特に必要とする指標です。

Answer 1

並べ替えは、余分なメモリを犠牲にして、オプションです。次のアルゴリズムを考えてみましょう。

1. Allocate additional array and copy into - O(n) 
2. Sort additional array - O(n lg n) 
3. Lop off the top k elements (in this case 5) - O(n), since k could be up to n 
4. Iterate over the original array - O(n) 
    4.a search the top k elements for to see if they contain the current element - O(lg n) 

したがって、ステップ4はソートと同様に（n * lg n）です。アルゴリズム全体はn lg nであり、非常に簡単にコーディングすることができます。

ここはすばやく汚れた例です。そこにバグがあり、明らかにヌルチェックなどが作用します。

import java.util.Arrays;

class ArrayTest { 

    public static void main(String[] args) { 
     int[] arr = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10}; 
     int[] indexes = indexesOfTopElements(arr,3); 
     for(int i = 0; i < indexes.length; i++) { 
      int index = indexes[i]; 
      System.out.println(index + " " + arr[index]); 
     } 
    } 

    static int[] indexesOfTopElements(int[] orig, int nummax) { 
     int[] copy = Arrays.copyOf(orig,orig.length); 
     Arrays.sort(copy); 
     int[] honey = Arrays.copyOfRange(copy,copy.length - nummax, copy.length); 
     int[] result = new int[nummax]; 
     int resultPos = 0; 
     for(int i = 0; i < orig.length; i++) { 
      int onTrial = orig[i]; 
      int index = Arrays.binarySearch(honey,onTrial); 
      if(index < 0) continue; 
      result[resultPos++] = i; 
     } 
     return result; 
    } 

} 

この操作のオーバーヘッドを減らすためにできることは他にもあります。たとえば、ソートの代わりに、最大のものを追跡するキューを使用することもできます。intこれらの値は、おそらくオーバーヘッドに重大な影響を与えるコレクションに追加されるボックスにする必要があります。

Answer 2

Arrays.sort（myArray）、最後の5つの要素を取ります。

元の注文を保存する場合は、コピーを並べ替えます。

インデックスが必要な場合は、Pythonやその他の言語にあるように、すばやく解決策はありません。あなたは並べ替えてスキャンしますが、それは醜いです。

あなたは客観的に行くことができます - これは結局Javaです。 ArrayMaxFilterオブジェクトを作成します。プライベートクラスのArrayElementを持ちます。このクラスは、インデックスと値で構成され、値によって自然順序付けされています。これは、int、indexとvalueのペアをとり、それらのArrayElementを作成し、それらを長さ5の優先度キューにドロップするメソッドを持ちます。アレイから各インデックス/値のペアを送信し、キューに残っている値を報告します。 （はい、プライオリティキューは伝統的に最低値を維持していますが、実装でこれを反転することができます）

Answer 3

私の素早く、「Think outside the box」アイデアは、最大値5を保持するEvictingQueue要素。配列の最初の5つの要素をあらかじめ入力しておく必要があります（昇順で行うため、最初に追加する要素は5つの要素の中で最も低くなります）。

現在の値がキューの最小値より大きい場合は、配列を繰り返し処理し、新しい要素をキューに追加する必要があります。索引を覚えておくには、ラッパー・オブジェクト（値/索引のペア）を作成します。

配列全体を反復処理した後、キューに5つの最大値/インデックスのペアが降順で表示されます。

これはO（n）ソリューションです。

Answer 4

私の解決策です。実行から

public static void main(String[] args){ 
    Random rand = new Random(); 
    int[] myArray = new int[10]; 
    IndiceValuePair[] pairs = new IndiceValuePair[5]; 
    System.out.println("Here are the indices and their values:"); 
    for(int i = 0; i < myArray.length; i++) { 
     myArray[i] = rand.nextInt(100); 
     System.out.println(i+ ": " + myArray[i]); 
     for(int j = 0; j < pairs.length; j++){ 
      //for the first five entries 
      if(pairs[j] == null){ 
       pairs[j] = new IndiceValuePair(i, myArray[i]); 
       break; 
      } 
      else if(pairs[j].getValue() < myArray[i]){ 
       //inserts the new pair into its correct spot 
       for(int k = 4; k > j; k--){ 
        pairs[k] = pairs [k-1]; 
       } 
       pairs[j] = new IndiceValuePair(i, myArray[i]); 
       break; 
      } 
     } 
    } 
    System.out.println("\n5 Max indices and their values"); 
    for(int i = 0; i < pairs.length; i++){ 
     System.out.println(pairs[i].getIndice() + ": " + pairs[i].getValue()); 
    } 
} 

と出力例：その後、

public class IndiceValuePair{ 
    private int indice; 
    private int value; 

    public IndiceValuePair(int ind, int val){ 
     indice = ind; 
     value = val; 
    } 
    public int getIndice(){ 
     return indice; 
    } 
    public int getValue(){ 
     return value; 
    } 
} 

とあなたの主な方法でこのクラスを使用します。値のペアindiceは、そのクラスを作成します

Here are the indices and their values: 
0: 13 
1: 71 
2: 45 
3: 38 
4: 43 
5: 9 
6: 4 
7: 5 
8: 59 
9: 60 

5 Max indices and their values 
1: 71 
9: 60 
8: 59 
2: 45 
4: 43 

私が提供した例では、0と99の間の値を持つ10のintを生成するだけで、それが機能することがわかりました。任意のサイズの1000値に合わせて簡単に変更できます。また、3つのループを別々に実行するのではなく、myArrayに追加した直後に私が追加する最新の値が最大値であるかどうかを調べました。あなたも、私が書いたこの機能を使用することができ、それを実行を与えると、それが答えに遅くあなた

Answer 5

ビットのために動作するかどうかを確認：

/** 
    * Return the indexes correspond to the top-k largest in an array. 
    */ 
public static int[] maxKIndex(double[] array, int top_k) { 
    double[] max = new double[top_k]; 
    int[] maxIndex = new int[top_k]; 
    Arrays.fill(max, Double.NEGATIVE_INFINITY); 
    Arrays.fill(maxIndex, -1); 

    top: for(int i = 0; i < array.length; i++) { 
     for(int j = 0; j < top_k; j++) { 
      if(array[i] > max[j]) { 
       for(int x = top_k - 1; x > j; x--) { 
        maxIndex[x] = maxIndex[x-1]; max[x] = max[x-1]; 
       } 
       maxIndex[j] = i; max[j] = array[i]; 
       continue top; 
      } 
     } 
    } 
    return maxIndex; 
}