Java dizisindeki n azami sayıları alın

Question

1000 tane boyut dizim var. Beş maksimum öğenin dizinlerini (dizinlerini) nasıl bulabilirim? Sorunun sürekli tüm azami elemanlarına en yüksek maksimum değer atama olmasıdır biliyoruz

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

:

kurulum kodu ve benim girişimi ile bir örnek

altında görüntülenir. Bunun nasıl düzeltileceğinden emin değilim çünkü myArray'un değerlerini ve endekslerini korumalıyım.

Sıralamaların bir seçenek olduğunu düşünmüyorum çünkü endeksleri korumam gerekiyor. Aslında, özellikle ihtiyacım olan indeksler.

Answer 1

Sıralama, fazla bellek pahasına bir seçenektir. Aşağıdaki algoritmayı düşünün.

Bu nedenle 4. adım (n * lg n), tıpkı sıralamadaki gibi. Tüm algoritma n lg n'dir ve kodlaması çok kolaydır.

İşte hızlı ve kirli bir örnek. İçinde hatalar olabilir ve açık olarak null kontrol ve benzeri şeyler devreye girer.

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

} 

Bu işlemin ek yükünü azaltmak için yapabileceğiniz başka şeyler de vardır. Örneğin, sıralama yerine, en büyük 5 parçasını izleyen bir sıra kullanmayı tercih edebilirsiniz. int s değerleri büyük olasılıkla bir eklemeye eklenecek bir kutuyu (muhtemelen kendiniz yuvarlanmadıkça) eklemek zorunda kalacaktır.

Answer 2

Arrays.sort (myArray), ardından son 5 öğeyi alın.

Orijinal siparişi korumak istiyorsanız bir kopyayı sıralayın.

Endeksleri istiyorsanız, python ya da başka dillerde olduğu için hızlı ve kirli bir çözüm yoktur. Sırala ve tara, ama bu çirkin.

Ya da itiraz edebilirsiniz - bu her şeyden önce java. ArrayMaxFilter nesnesini oluşturun. Bir indeks ve bir değerden oluşan ve değere göre doğal bir siparişe sahip olan özel bir ArrayElement sınıfına sahip olacak. Bir çift indeksi, indeksi ve değeri alan, bir ArrayElement'i oluşturan ve bunları 5. uzunlukta bir öncelik kuyruğuna düşüren bir yönteme (ya da bulmak istediğiniz bir çoğuna) sahip olacak. Her bir dizin/değer çiftini diziden gönderin, ardından kuyrukta kalan değerleri bildirin. (Evet, bir öncelik sırası geleneksel olarak en düşük değerleri korur, ancak bunu uygulamanızda ters çevirebilirsiniz)

Answer 3

Hızlı ve biraz "kutunun dışında düşünün" fikri en fazla 5 tutan EvictingQueue kullanmak olacaktır elementler. Bunu, dizinizden ilk beş öğe ile doldurmak zorunda kaldınız (artan düzende yapın, böylece eklediğiniz ilk öğe beşten en düşük olanıdır). Dizide yinelemeli ve sıradaki değer kuyruğun en düşük değerinden büyük olduğunda sıraya yeni bir öğe eklemelisiniz. Dizinleri hatırlamak için bir sarmalayıcı nesnesi (bir değer/dizin çifti) oluşturun.

Dizinin tamamını yineledikten sonra, sıraya göre beş maksimum değer/dizin çiftinize sahip olursunuz (azalan sırada).

Bu bir O (n) çözümü.

Answer 4

İşte benim çözümüm. Bir sınıf oluşturmak çiftlerinden bir değer ile bir indis:

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

ve daha sonra ana yöntemde Bu sınıfı:

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: bir çalışmadan elde

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

ve örnek çıktı verdiğim örnek, sadece çalıştığını görebilmem için 0 ile 99 arasında bir değere sahip olan on inç üretir. Her boyutta 1000 değere sığdırmak için bunu kolayca değiştirebilirsiniz. Ayrıca, döngüler için 3 ayrı çalıştırmak yerine, eklediğim en yeni değerin myArray'a ekledikten sonra bir maksimum değer olup olmadığını kontrol ettim. Ayrıca yazdığım bu fonksiyonu kullanabilirsiniz, it a koşmak verin ve onu yanıtlayan geç sen

Answer 5

biraz çalıştığını görmek:

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