«Как найти самый большой элемент в 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. QuickSelect

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

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

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

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

Выберите опорный элемент и соответствующим образом разделите массив. Выберите самый правый элемент в качестве опорного. Перетасуйте массив таким образом, чтобы опорный элемент располагался на своем законном месте — все элементы меньше, чем опорная, будет иметь более низкие индексы, а элементы, большие, чем опорная, будут помещены в более высокие индексы, чем опорная. позиция больше, чем 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 With Randomized Partition

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

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

Вместо вызова 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).