Java, обнаружение наибольшего значения Kth из массива

У меня было интервью с Facebook, и они задали мне этот вопрос.

Предположим, что у вас есть неупорядоченный массив с N различными значениями

$input = [3,6,2,8,9,4,5]

Реализовать функцию, которая находит наибольшее значение Kth.

EG: Если K = 0, верните 9. Если K = 1, верните 8.

Я сделал этот метод.

private static int getMax(Integer[] input, int k)
{
    List<Integer> list = Arrays.asList(input);
    Set<Integer> set = new TreeSet<Integer>(list);

    list = new ArrayList<Integer>(set);
    int value = (list.size() - 1) - k;

    return list.get(value);
}

Я только что протестировал, и метод отлично работает на основе вопроса. Однако, интервьюируемый сказал: in order to make your life complex! lets assume that your array contains millions of numbers then your listing becomes too slow. What you do in this case? В качестве намека он предложил использовать min heap. Основываясь на моих знаниях, каждое дочернее значение кучи не должно быть больше корневого значения. Итак, в этом случае, если мы предположим, что 3 является корнем, то 6 является его дочерним, а его значение больше, чем значение root. Возможно, я ошибаюсь, но что вы думаете и какова его реализация на основе min heap?

Ответ 1

Он действительно дал вам весь ответ. Не просто подсказка.

И ваше понимание основано на max heap. Не min heap. И эта работа не требует пояснений.

В минимальной куче корень имеет значение minimum (меньше его детей).

Итак, вам нужно, перебрать массив и заполнить элементы K в min heap. Как только это произойдет, куча автоматически содержит наименьшее значение в корне.

Теперь, для каждого элемента (next), который вы читаете из массива, - > проверьте, больше ли значение, чем корень из минимальной кучи. - > Если да, удалите корень из мини-кучи и добавьте к нему значение.

После того, как вы пройдете весь массив, корень min heap будет автоматически содержать K th самый большой элемент.

И все остальные элементы (точнее, k-1 элементов) в куче будут больше, чем K.

Ответ 2

Вот реализация Min Heap с помощью PriorityQueue в java. Сложность: n * log k.

import java.util.PriorityQueue;

public class LargestK {

  private static Integer largestK(Integer array[], int k) {
    PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k+1);
    int i = 0;
    while (i<=k) {
      queue.add(array[i]);
      i++;
    }
    for (; i<array.length; i++) {
      Integer value = queue.peek();
      if (array[i] > value) {
        queue.poll();
        queue.add(array[i]);
      }
    }
    return queue.peek();
  }

  public static void main(String[] args) {
    Integer array[] = new Integer[] {3,6,2,8,9,4,5};
    System.out.println(largestK(array, 3));
  }
}

Выход: 5

Цикл кода над массивом, который O(n). Размер PriorityQueue (Min Heap) равен k, поэтому любая операция будет log k. В худшем случае, когда все номера отсортированы ASC, сложность n*log k, потому что для каждого элемента вам нужно удалить верхнюю часть кучи и вставить новую элемент.

Ответ 3

Изменить: Отметьте ответ для решения O (n).

Возможно, вы можете использовать PriorityQueue, чтобы решить эту проблему:

public int findKthLargest(int[] nums, int k) {
        int p = 0;
        int numElements = nums.length;
        // create priority queue where all the elements of nums will be stored
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

        // place all the elements of the array to this priority queue
        for (int n : nums){
            pq.add(n);
        }

        // extract the kth largest element
        while (numElements-k+1 > 0){
            p = pq.poll();
            k++;
        }

        return p;
    }

Из Java doc:

Замечание по реализации: эта реализация обеспечивает O (log (n)) время для методы ввода и удаления (offer, poll, remove() и add); линейное время для remove(Object) и contains(Object)методы; и постоянное время для методов поиска (peek, element и size).

В цикле for выполняется n раз, и сложность алгоритма выше O(nlogn).

Ответ 4

Решение на основе кучи идеально подходит, если количество элементов в массиве/потоке неизвестно. Но, если они конечны, но все же вы хотите оптимизированное решение в линейном времени.

Мы можем использовать Quick Select, обсуждаем здесь.

Массив = [3,6,2,8,9,4,5]

Позвольте выбрать опорный элемент как первый элемент:

pivot = 3 (при 0-м индексе),

Теперь разделите массив таким образом, чтобы все элементы, меньшие или равные, находились с левой стороны и цифры больше 3 с правой стороны. Как это сделано в Quick Sort (обсуждалось на моем blog).

Итак, после первого прохода - [2, 3, 6,8,9,4,5]

индекс pivot равен 1 (т.е. второму нижнему элементу). Теперь примените тот же процесс снова.

выбрал, теперь 6, значение в индексе после предыдущего поворота - [2,3,4,5, 6, 8,9]

Итак, теперь 6 находится в нужном месте.

Продолжайте проверять, найдено ли вы соответствующее число (k-е место по величине или k-е место на каждой итерации). Если он обнаружит, что вы сделали, продолжайте.

Ответ 5

Один подход для постоянных значений k заключается в использовании частичной сортировки вставки.

(Это предполагает различные значения, но может быть легко изменено для работы с дубликатами)

last_min = -inf
output = []
for i in (0..k)
    min = +inf
    for value in input_array
        if value < min and value > last_min
            min = value
    output[i] = min
print output[k-1]

(Этот псевдокод, но должен быть достаточно простым для реализации на Java).

Общая сложность O(n*k), что означает, что она работает очень хорошо, если и только если k является константой или, как известно, меньше log(n).

В плюсе это очень простое решение. С минусовой стороны это не так эффективно, как кучное решение