suche viele min in java

Question

ich bin neuling in java. Ich habe viele Min-Probleme in Java. Ich habe große Daten. aber Beispieldaten wie folgt.

k[][] = [74 85 123 
       73 84 122 
       72 83 121 
       70 81 119 
       69 80 118 
       76 87 125 
       77 88 126 
       78 89 127]; 

und ich möchte Ausgabe wie folgt.

min1 = 69 min1 = 80 min1 = 118 
min2 = 70 min2 = 81 min2 = 119 
min3 = 72 min3 = 83 min3 = 121 

Ich verwende Sortierung in diesen Daten, aber die Ergebnisse sind nicht effizient. mir jemand helfen thx

Answer 1

Sagen Sie Ihre Daten hat N Zeilen und M Spalten

1. Iterate über jede Spalte
2. alle Elemente in der Spalte hinzufügen in eine minHeap (min Prioritätswarteschlange)
3. Abrufen der ersten 3 Zahlen aus dem minHeap (dies sind die 3 Minuten)
4. Löschen Sie die Warteschlange und gehen Sie zur nächsten Spalte

O (n) Raum, O (M N lg (N)) Zeit

Answer 2

Hier ist eine allgemeine Implementierung einer Hilfsklasse für die Suche nach den niedrigsten X ganzen Zahlen verwenden.

Mit drei Spalten werden drei Instanzen der Hilfsklasse erstellt, und die Daten werden anschließend iteriert, um die 3 niedrigsten Werte für jede Spalte zu erfassen.

Die Vorteile dieses Codes sind:

• behält nur die niedrigsten X-Werte
• nicht die ganzen Zahlen
• verwendet binäre Suche für eine verbesserte Leistung von höheren Werten von X

zu boxen Braucht

Dies bedeutet, dass es schnell sein sollte und einen geringen Speicherbedarf haben sollte, der unbegrenzte Datenmengen unterstützt (wenn gestreamt wird).

Eine Demo finden Sie unter IDEONE.

import java.util.Arrays; 

class Ideone { 
    private static final int MIN_COUNT = 3; 
    public static void main(String[] args) { 
     int[][] data = { { 74, 85, 123 }, 
         { 73, 84, 122 }, 
         { 72, 83, 121 }, 
         { 70, 81, 119 }, 
         { 69, 80, 118 }, 
         { 76, 87, 125 }, 
         { 77, 88, 126 }, 
         { 78, 89, 127 } }; 
     // Initialize min collectors 
     Min[] min = new Min[data[0].length]; 
     for (int col = 0; col < min.length; col++) 
      min[col] = new Min(MIN_COUNT); 
     // Collect data 
     for (int row = 0; row < data.length; row++) 
      for (int col = 0; col < min.length; col++) 
       min[col].add(data[row][col]); 
     // Print result 
     for (int i = 0; i < MIN_COUNT; i++) { 
      for (int col = 0; col < min.length; col++) 
       System.out.printf("min%d = %-5d ", i + 1, min[col].get(i)); 
      System.out.println(); 
     } 
    } 
} 
class Min { 
    private int[] min; 
    public Min(int count) { 
     this.min = new int[count]; 
     Arrays.fill(this.min, Integer.MAX_VALUE); 
    } 
    public void add(int value) { 
     int idx = Arrays.binarySearch(this.min, value); 
     if (idx != -this.min.length - 1) { // not insert at end 
      if (idx < 0) 
       idx = -idx - 1; 
      System.arraycopy(this.min, idx, this.min, idx + 1, this.min.length - idx - 1); 
      this.min[idx] = value; 
     } 
    } 
    public int get(int index) { 
     return this.min[index]; 
    } 
}