Ottieni indici di n massimi in array java

Question

Ho una matrice di dimensione 1000. Come posso trovare gli indici (indici) dei cinque elementi massimi?

Un esempio con il codice di setup e il mio tentativo vengono visualizzati sotto:

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

So che il problema è che è costantemente assegnando il più alto valore massimo a tutti gli elementi massimi. Non sono sicuro di come rimediare perché devo conservare i valori e gli indici di myArray.

Non penso che lo smistamento sia un'opzione perché ho bisogno di preservare gli indici. In effetti, sono gli indici di cui ho bisogno in particolare.

Answer 1

L'ordinamento è un'opzione, a scapito della memoria aggiuntiva. Considera il seguente algoritmo.

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) 

Quindi passo 4 è (n * lg n), proprio come il genere. L'intero algoritmo è n lg n ed è molto semplice da codificare.

Ecco un esempio rapido e sporco. Potrebbero esserci dei bug, e ovviamente entrano in gioco controlli nulli e simili.

importazione java.util.Array;

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

} 

Ci sono altre cose che puoi fare per ridurre il sovraccarico di questa operazione. Ad esempio, invece di ordinare, puoi scegliere di utilizzare una coda che tiene traccia dei 5 più grandi. Essendo int, probabilmente i valori dovrebbero essere inseriti in una raccolta (a meno che tu non abbia eseguito il rollover) che aggiunge un sovraccarico in modo significativo.

Answer 2

Arrays.sort (myArray), quindi prendere gli ultimi 5 elementi.

Ordinare una copia se si desidera mantenere l'ordine originale.

Se si desidera che gli indici, non vi è una soluzione rapida e sporca come ci sarebbe in Python o in altri linguaggi. Puoi ordinare e scansionare, ma è brutto.

Oppure potresti diventare un po 'noioso, dopotutto questo è java. Crea un oggetto ArrayMaxFilter. Avrà una classe privata ArrayElement, che consiste in un indice e un valore e ha un ordine naturale in base al valore. Avrà un metodo che prende una coppia di interi, indice e valore, crea un ArrayElement di loro e li colloca in una coda di priorità di lunghezza 5. (o comunque molti si vuole trovare). Invia ogni coppia indice/valore dall'array, quindi segnala i valori rimanenti nella coda. (sì, una coda di priorità mantiene tradizionalmente i valori più bassi, ma è possibile capovolgerla nell'implementazione)

Answer 3

La mia idea veloce e un po '"fuori dagli schemi" sarebbe utilizzare lo EvictingQueue che contiene un massimo di 5 elementi. Hai dovuto pre-riempirlo con i primi cinque elementi dell'array (fallo in ordine crescente, quindi il primo elemento che aggiungi è il più basso tra i cinque).

Quindi è necessario ripetere l'array e aggiungere un nuovo elemento alla coda ogni volta che il valore corrente è maggiore del valore più basso nella coda. Per ricordare gli indici, creare un oggetto wrapper (una coppia valore/indice).

Dopo aver eseguito l'iterazione dell'intero array, si hanno le cinque coppie valore/indice massimi nella coda (in ordine decrescente).

È una soluzione O (n).

Answer 4

Ecco la mia soluzione. Creare una classe che paia un Indice I con un valore:

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

e quindi utilizzare questa classe nel metodo principale:

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

e l'esempio di uscita da una corsa:

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 

Il l'esempio che ho fornito genera solo dieci int in un valore compreso tra 0 e 99 solo per poter vedere che ha funzionato. Puoi facilmente modificarlo per adattare 1000 valori di qualsiasi dimensione. Inoltre, anziché eseguire 3 loop separati, ho verificato se il valore più recente che aggiungo è un valore massimo subito dopo aver aggiunto a myArray. Dare un giro e vedere se funziona per voi

Answer 5

un po 'in ritardo nel rispondere, si potrebbe anche utilizzare questa funzione che ho scritto:

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