Pobierz indeksy n maks. W tablicy java

Question

Mam tablicę o rozmiarze 1000. Jak mogę znaleźć indeksy (indeksy) pięciu maksymalnych elementów?

Przykładem z kodem konfiguracji i moje próby są wyświetlane poniżej:

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

wiem, że problemem jest to, że jest on stale przypisywania najwyższą wartość maksymalną dla wszystkich maksymalnych elementów. Nie jestem pewien, jak temu zaradzić, ponieważ muszę zachować wartości i indeksy myArray.

Nie sądzę, że sortowanie jest opcją, ponieważ muszę zachować indeksy. Rzeczywiście, potrzebuję konkretnie indeksów.

Answer 1

Sortowanie jest opcją, kosztem dodatkowej pamięci. Rozważmy następujący algorytm.

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) 

Tak więc krok 4 to (n * lg n), podobnie jak sortowanie. Cały algorytm jest n lg n i jest bardzo prosty w kodzie.

Oto szybki i brudny przykład. Mogą w nim występować błędy i oczywiście sprawdzanie wartości null i tym podobne wchodzą w grę.

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

} 

Są inne rzeczy, które można zrobić, aby zmniejszyć obciążenie związane z tą operacją. Na przykład zamiast sortowania, możesz zdecydować się na użycie kolejki, która śledzi największe wartości. Będą one prawdopodobnie wymagały boksowania, aby zostać dodane do kolekcji (o ile nie została ona rozwinięta), co znacznie zwiększa obciążenie.

Answer 2

Arrays.sort (myArray), a następnie weź ostatnie 5 elementów.

Sortuj kopię, jeśli chcesz zachować oryginalną kolejność.

Jeśli chcesz indeksów, nie ma szybkie i brudne rozwiązanie, jak byłoby w Pythonie lub w niektórych innych językach. Sortujesz i skanujesz, ale to jest brzydkie.

Albo możesz przejść objecty - w końcu to java. Utwórz obiekt ArrayMaxFilter. Będzie mieć prywatną klasę ArrayElement, która składa się z indeksu i wartości i ma naturalne uporządkowanie według wartości. Będzie miał metodę, która pobiera parę wartości, indeks i wartość, tworzy ich ArrayElement i upuszcza je w kolejce o priorytecie długości 5. (lub jakkolwiek wiele z nich chcesz znaleźć). Prześlij każdą parę indeks/wartość z tablicy, a następnie zgłoś wartości pozostałe w kolejce. (tak, kolejka priorytetowa tradycyjnie zachowuje najniższe wartości, ale można to odwrócić w implementacji)

Answer 3

Mój pomysł "myśl poza domem" jest szybki i może posłużyć się EvictingQueue, który może pomieścić maksymalnie 5 elementy. Musiałeś wstępnie wypełnić go pierwszymi pięcioma elementami z twojej tablicy (zrób to w porządku rosnącym, więc pierwszy dodany element jest najniższy z pięciu).

Niż trzeba powtórzyć przez tablicę i dodać nowy element do kolejki, gdy bieżąca wartość jest większa niż najniższa wartość w kolejce. Aby zapamiętać indeksy, utwórz obiekt opakowania (parę wartość/indeks).

Po przejrzeniu całej tablicy, masz pięć maksymalnej pary wartości/indeksu w kolejce (w kolejności malejącej).

To rozwiązanie O (n).

Answer 4

Oto moje rozwiązanie. Utworzyć klasę, która pary índice o wartości:

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

a następnie użyć tej klasy w głównym sposobem:

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

i przykład wyjście z run:

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 

The przykład podany tylko generuje dziesięć int z wartością od 0 do 99 tylko po to, aby zobaczyć, że zadziałało. Możesz łatwo zmienić to, aby dopasować 1000 wartości o dowolnym rozmiarze. Ponadto, zamiast uruchamiać 3 osobne pętle, sprawdziłem, czy ostatnia dodana wartość jest wartością maksymalną zaraz po dodaniu do myArray. Nadać jej bieg i sprawdzić, czy to działa dla Ciebie

Answer 5

trochę późno w odpowiedzi, można również korzystać z tej funkcji, że napisałem:

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