K-й самый большой элемент в массиве — быстрый выбор с использованием схемы разбиения Lomuto.

Согласно Leetcode:

Мы настоятельно рекомендуем K-й самый большой элемент в массиве, который много раз задавали в телефонном интервью Amazon.

Задача

По заданному массиву целых чисел nums и целому числу k вернуть самый k-й самый большой элемент в массив.

Обратите внимание, что это k-й самый большой элемент в отсортированном порядке, а не k-й отдельный элемент.

Вы должны решить его за время O(n).

Куча

Есть несколько способов решить эту задачу. Самый простой способ — выполнить итерацию по массиву и сохранить верхний K-й по величине элемент во время итерации. Для этой цели куча является лучшей структурой данных.

Алгоритм:

1. перебирать массив и помещать каждый элемент в кучу
2. если размер кучи больше k - удалить наименьшую (которая будет в начале нашей очереди)
3. возвратить первый элемент

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int n: nums) {
          heap.add(n);
          if (heap.size() > k)
            heap.poll();
        }

        return heap.poll();        
  }
}

Мы перебираем массив и каждый раз вставляем элемент в кучу длиной K, поэтому временная сложность равна O(NlogK). Можем ли мы сделать лучше? :)

Быстрый выбор временной сложности

Сначала давайте обсудим высокоуровневый дизайн, а затем мы сможем углубиться. Вот ссылка на проблему.

Нам нужно найти K-й по величине элемент в массиве. Так как для нас удобнее сортировать массив в порядке неубывания, перефразируем задачу и скажем, что нам нужно найти N-k наименьший элемент в массиве.

Идея алгоритма заключается в использовании алгоритма разделения из quickselect.

Мы разбиваем весь массив (O(n) временная сложность).

Затем отбросить половину и продолжить с другой половиной (O(n/2) временная сложность).

Снова удалите половину и продолжите с 1/4 исходного массива (O(n/4) временная сложность).

Продолжайте делать это, пока не дойдете до одного элемента. Подводя итог общей временной сложности:

n + n/2 + n/4 + n/8 +... ~ 2n = n

Вы можете быть сбиты с толку временной сложностью, думая: «Подождите, мы делаем почти то же самое с бинарным поиском, это logN временная сложность, где logN часть». Что ж, вы правы. Ключевым моментом здесь является то, что не все разделы выполняют одинаковый объем работы.

Этот более точный анализ, в котором используется тот факт, что проделанная работа продолжает уменьшаться на каждой итерации, дает время выполнения O(n).

Если вы все еще смущены временной сложностью, взгляните на этот ответ и эту статью.

Алгоритм разделения (схема разделения Ломуто)

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

Самое сложное в этом алгоритме — понять, как работает раздел. Представим, что у нас есть массив [2,6,3,4,7,1,8,5]. Со схемой разбиения Lomuto алгоритм будет выглядеть следующим образом:

1. выбрать последний элемент в качестве опорного
2. создайте 2 указателя, i и startIndex, начиная с начала целевого интервала.
3. Первый указатель i просканирует весь интервал и проверит условие — если значение в i меньше опорного, замените его значением в указателе. startIndex и увеличить startIndex
4. замените опорную точку (которая находится в конце массива) на значение в startIndex (поскольку это место для нашего опорного значения) и верните startIndex .

Для этого нам нужен один цикл for и выделенная переменная startIndex, которая равна индексу первого элемента в массиве (в нашем случае это 0).

Теперь у нас получилось значение storeIndex = 3, которое на самом деле является местом для нашего сводного элемента. Мы можем поменять их местами и вернуть этот опорный индекс. Массив имеет вид [2,3,4,5,7,6], опорный индекс равен 3.

public void swap(int i, int j) {
  int temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}

public int partition(int start, int end) {
  int pivot = nums[end];
  int storeIndex = start;
  for (int i = start; i <= end; i++) {
    if (nums[i] < pivot) {
      swap(i, storeIndex);
      storeIndex++;
    }
  }
  //don't forget to move pivot element from the end of the array to its position
  swap(end, storeIndex);
  return storeIndex;
}

Случайный поворот

Наихудшим случаем этого алгоритма будет O(n^2). Почему это так? Алгоритм чувствителен к выбранной опорной точке. Представьте, что вы уже отсортировали массив и каждый раз выбираете первый элемент в качестве опорного. Это означает, что каждый раздел будет уменьшать диапазон элементов только на 1. Чтобы избежать этого, нам нужно каждый раз выбирать случайный опорный элемент:

Random random = new Random();
//asume that 'start' is an index of the first element in search interval of the array
//and 'end' is an index of the last element in that interval, then:
int pivot = left + random.nextInt(right - left);

Алгоритм быстрого выбора

Наконец, нам нужно реализовать алгоритм быстрого выбора. Шаги:

* выберите случайный опорный пункт * разбить массив с помощью этой опорной точки и вернуть ее новый индекс * если индекс равен N - k, то находим свое значение, иначе выбираем одну из двух частей массива, и повторяем алгоритм

Вот исходный код:

class Solution {
    int[] nums;
    public void swap(int i, int j) {
      int temp = nums[i];
      nums[i] = nums[j];
      nums[j] = temp;
    }

    public int partition(int start, int end, int pivotIndex) {
      int pivot = nums[pivotIndex];
      //move pivot to the end of the array;
      swap(end, pivotIndex);
      int startIndex = start;
      for (int i = start; i <= end; i++) {
        if (nums[i] < pivot) {
          swap(i, startIndex);
          startIndex++;
        }
      }
      //don't forget to move pivot element from the end of the array to its position
      swap(end, startIndex);
      return startIndex;
    }
    public int findKthLargest(int[] nums, int k) {
        this.nums = nums;
        return quickselect(0, nums.length - 1, nums.length - k);
    }
    public int quickselect(int start, int end, int k) {
        if (start == end) {
            return nums[start];
        }
        Random random = new Random();
        int pivotIndex = start + random.nextInt(end - start);
        pivotIndex = partition(start, end, pivotIndex);
        if (pivotIndex == k) {
            return nums[pivotIndex];
        }
        if (pivotIndex < k) {
            return quickselect(pivotIndex + 1, end, k);
        }
        return quickselect(start, pivotIndex - 1, k);
    }
}