9

サイズ 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。

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

4

6 に答える 6

6

ソートはオプションですが、余分なメモリを消費します。次のアルゴリズムを検討してください。

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 であり、コーディングは非常に簡単です。

これは簡単で汚い例です。バグが含まれている可能性があり、明らかに null チェックなどが機能します。

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;
    }

}

この操作のオーバーヘッドを削減するためにできることは他にもあります。たとえば、並べ替えの代わりに、最大の 5 を追跡するキューを使用することを選択できます。intこれらの値は、コレクションに追加するためにおそらくボックス化する必要があり (独自にロールしない限り)、オーバーヘッドが大幅に増加します。

于 2013-07-12T20:29:48.933 に答える
3

回答が少し遅れましたが、私が書いたこの関数を使用することもできます:

/**
  * 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;
}
于 2014-07-26T08:24:40.600 に答える
0

これが私の解決策です。インデックスと値をペアにするクラスを作成します。

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;
    }
}

次に、メイン メソッドでこのクラスを使用します。

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());
    }
}

および実行からの出力例:

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 つの個別の for ループを実行するのではなく、 to に追加した直後に、追加した最新の値が最大値であるかどうかを確認しましたmyArray。それを実行して、それがあなたのために働くかどうか見てください

于 2013-07-12T21:21:52.300 に答える