Как найти самый большой элемент в Java

1. Введение

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

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

2. Решения

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

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

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

Определим необходимые шаги:

• Отсортировать массив в порядке возрастания
• Поскольку последний элемент массива будет самым большим элементом, k -й самый большой элемент будет иметь индекс x, где 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) -му индексу:

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

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

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

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

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

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

• Выберите опорный элемент и разделите массив соответствующим образом.

• Выберите крайний правый элемент в качестве опорного

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

• Если стержень находится в k -м элементе массива, выйти из процесса, так как стержень - это k -й самый большой элемент

• Если позиция поворота больше k, то продолжить процесс с левым подмассивом, в противном случае повторить процесс с правым подмассивом

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

Если мы отсортируем массив в порядке возрастания, k -й элемент массива будет k -м наименьшим элементом. Чтобы найти k -й самый большой элемент, мы можем передать k= length(Array) – 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;
}

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

Точно так же элементы с более высокими индексами будут больше, чем опорный элемент:

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. QuickSelect со случайным разделением

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

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

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

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

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);
}

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

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

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

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

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

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

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