Рубрики
Без рубрики

Как найти K-й по величине элемент в Java

Изучите несколько подходов к нахождению k-го по величине элемента в наборе уникальных чисел с помощью Java.

Автор оригинала: baeldung.

1. введение

В этой статье мы представим различные решения для нахождения k – го наибольшего элемента в последовательности уникальных чисел. В наших примерах мы будем использовать массив целых чисел.

Мы также поговорим о средней и наихудшей временной сложности каждого алгоритма.

2. Решения

Теперь давайте рассмотрим несколько возможных решений — одно с использованием простой сортировки и два с использованием алгоритма быстрого выбора, полученного из быстрой сортировки.

2.1. Сортировка

Когда мы думаем о проблеме, возможно, самое очевидное решение, которое приходит на ум, – это | сортировка массива .

Давайте определим необходимые шаги:

  • Сортировка массива в порядке возрастания
  • Поскольку последний элемент массива будет самым большим элементом, то k – й самый большой элемент будет находиться в индексе , где x(массив) – k

Как мы видим, решение простое, но требует сортировки всего массива. Следовательно, временная сложность будет O(n*logn) :

public int findKthLargestBySorting(Integer[] arr, int k) {
    Arrays.sort(arr);
    int targetIndex = arr.length - k;
    return arr[targetIndex];
}

Альтернативный подход состоит в том, чтобы отсортировать массив в порядке убывания и просто вернуть элемент по индексу (k-1) th:

public int findKthLargestBySortingDesc(Integer[] arr, int k) {
    Arrays.sort(arr, Collections.reverseOrder());
    return arr[k-1];
}

2.2. Быстрый выбор

Это можно считать оптимизацией предыдущего подхода. В этом случае мы выбираем QuickSort для сортировки. Анализируя постановку задачи, мы понимаем, что на самом деле нам не нужно сортировать весь массив — нам нужно только переставить его содержимое так, чтобы k – й элемент массива был k – м самым большим или самым маленьким.

В QuickSort мы выбираем элемент поворота и перемещаем его в правильное положение. Мы также разделяем массив вокруг него. В Quick Select идея состоит в том, чтобы остановиться в точке, где сам стержень является k – м самым большим элементом.

Мы можем оптимизировать алгоритм дальше, если не будем повторяться как для левой, так и для правой сторон разворота. Нам нужно только повторить для одного из них в соответствии с положением оси вращения.

Давайте рассмотрим основные идеи алгоритма быстрого выбора:

  • Выберите сводный элемент и разделите массив соответствующим образом
    • Выберите самый правый элемент в качестве точки поворота
    • Перетасуйте массив таким образом, чтобы элемент pivot был помещен на свое законное место — все элементы, меньшие, чем pivot, будут иметь более низкие индексы, а элементы, большие, чем pivot, будут помещены в более высокие индексы, чем pivot
  • Если pivot помещен в k – й элемент массива, завершите процесс, так как pivot является k – м самым большим элементом
  • Если положение поворота больше k, затем продолжите процесс с левым подмассивом, в противном случае повторите процесс с правым подмассивом

Мы можем написать общую логику, которая также может быть использована для поиска k – го наименьшего элемента. Мы определим метод findKthElement с помощью QuickSelect () , который вернет k – й элемент в отсортированном массиве.

Если мы отсортируем массив в порядке возрастания, то k – й элемент массива будет k – м наименьшим элементом. Чтобы найти k – й самый большой элемент, мы можем передать k= длина(массив) – k.

Давайте реализуем это решение:

public int 
  findKthElementByQuickSelect(Integer[] arr, int left, int right, int k) {
    if (k >= 0 && k <= right - left + 1) {
        int pos = partition(arr, left, right);
        if (pos - left == k) {
            return arr[pos];
        }
        if (pos - left > k) {
            return findKthElementByQuickSelect(arr, left, pos - 1, k);
        }
        return findKthElementByQuickSelect(arr, pos + 1,
          right, k - pos + left - 1);
    }
    return 0;
}

Теперь давайте реализуем метод partition , который выбирает самый правый элемент в качестве опорного, помещает его в соответствующий индекс и разбивает массив таким образом, чтобы элементы с более низкими индексами были меньше, чем элемент pivot.

Аналогично, элементы с более высокими индексами будут больше, чем элемент pivot:

public int partition(Integer[] arr, int left, int right) {
    int pivot = arr[right];
    Integer[] leftArr;
    Integer[] rightArr;

    leftArr = IntStream.range(left, right)
      .filter(i -> arr[i] < pivot)
      .map(i -> arr[i])
      .boxed()
      .toArray(Integer[]::new);

    rightArr = IntStream.range(left, right)
      .filter(i -> arr[i] > pivot)
      .map(i -> arr[i])
      .boxed()
      .toArray(Integer[]::new);

    int leftArraySize = leftArr.length;
    System.arraycopy(leftArr, 0, arr, left, leftArraySize);
    arr[leftArraySize+left] = pivot;
    System.arraycopy(rightArr, 0, arr, left + leftArraySize + 1,
      rightArr.length);

    return left + leftArraySize;
}

Существует более простой, итеративный подход для достижения разделения:

public int partitionIterative(Integer[] arr, int left, int right) {
    int pivot = arr[right], i = left;
    for (int j = left; j <= right - 1; j++) {
        if (arr[j] <= pivot) {
            swap(arr, i, j);
            i++;
        }
    }
    swap(arr, i, right);
    return i;
}

public void swap(Integer[] arr, int n1, int n2) {
    int temp = arr[n2];
    arr[n2] = arr[n1];
    arr[n1] = temp;
}

Это решение работает в среднем за O(n) время. Однако в худшем случае временная сложность будет O(n^2) .

2.3. Быстрый Выбор С Рандомизированным Разделением

Этот подход является небольшой модификацией предыдущего подхода. Если массив почти/полностью отсортирован и если мы выберем самый правый элемент в качестве оси, разделение левого и правого подмассивов будет очень неравномерным.

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

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

Давайте реализуем метод random Partition :

public int randomPartition(Integer arr[], int left, int right) {
    int n = right - left + 1;
    int pivot = (int) (Math.random()) * n;
    swap(arr, left + pivot, right);
    return partition(arr, left, right);
}

В большинстве случаев это решение работает лучше, чем в предыдущем случае.

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

Однако наихудшая временная сложность все еще остается O(n^2) .

3. Заключение

В этой статье мы обсудили различные решения для поиска k – го самого большого (или самого маленького) элемента в массиве уникальных чисел. Самое простое решение-отсортировать массив и вернуть элемент k th. Это решение имеет временную сложность O(n*logn) .

Мы также обсудили два варианта быстрого выбора. Этот алгоритм не является простым, но он имеет временную сложность O(n) в средних случаях.

Как всегда, полный код алгоритма можно найти на GitHub .

Читайте ещё по теме: