поиск много мин в java

Question

Я новичок в java. У меня есть проблема поиска много минут в java. У меня большие данные. но пример таких данных.

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

и я хочу выход как это.

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

Я использую сортировку по этим данным, но результаты неэффективны. кто-то поможет мне ТНХ

Answer 1

Произнесите данных имеет N строк и М столбцов

1. Итерация по каждой колонке
2. Добавить все элементы в столбце в (приоритет очереди мин) в minHeap
3. Извлеките первые 3 числа из minHeap (это будет 3 минуты)
4. Очистить очередь и перейти к следующей колонке

О (п) пространство, О (М N LG (N)) Время

Answer 2

Вот общий реализация с использованием вспомогательного класса для нахождения самых низких X целых чисел.

С тремя столбцами создается три экземпляра класса-помощника, а затем данные повторяются для сбора 3 самых низких значений для каждого столбца.

Преимущества этого кода:

• только сохраняет низкий X значения
• Не нужно боксировать целые числа
• Использует бинарный поиск для повышения производительности более высоких значений X

Это означает, что он должен быть быстрым и иметь низкий объем памяти, поддерживающий неограниченное количество данных (если потоковое).

См. 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]; 
    } 
}