Как да намерите най-големия елемент в Java

1. Въведение

В тази статия ще представим различни решения за намиране на k -тия най-голям елемент в последователност от уникални числа. За нашите примери ще използваме масив от цели числа.

Ще говорим и за средната и най-лошата времева сложност на всеки алгоритъм.

2. Решения

Сега нека разгледаме няколко възможни решения - едно, използващо обикновен сортиране, и две, използващи алгоритъма за бърз избор, извлечен от Quick Sort.

2.1. Сортиране

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

Нека дефинираме необходимите стъпки:

  • Сортирайте масива във възходящ ред
  • Тъй като последният елемент от масива ще бъде най-големият елемент, k -тият най-голям елемент ще бъде с xth индекс, където 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:

  • Изберете въртящ елемент и съответно разделете масива
    • Изберете най-десния елемент като ос
    • Разбъркайте масива така, че елементът на въртене да е поставен на законното му място - всички елементи, по-малки от пивота, ще бъдат с по-ниски индекси, а елементи, по-големи от pivot, ще бъдат поставени при по-високи индекси от pivot
  • Ако pivot е поставен в k -тия елемент в масива, излезте от процеса, тъй като pivot е k -тият най-голям елемент
  • Ако позицията на въртене е по-голяма от k, продължете процеса с левия подмасив, в противен случай повторете процеса с десния подмасив

Можем да напишем обща логика, която може да се използва и за намиране на k -тия най-малък елемент. Ще дефинираме метод findKthElementByQuickSelect (), който ще върне k -тия елемент в сортирания масив.

Ако сортираме масива във възходящ ред, k -тият елемент на масива ще бъде k -тият най-малък елемент. За да намерим k -ия най-голям елемент, можем да предадем k = дължина (масив) - k.

Нека приложим това решение:

public int findKthElementByQuickSelect(Integer[] arr, int left, int right, int k) { if (k >= 0 && k  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]  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. Бърз избор с рандомизиран дял

Този подход е малка модификация на предишния подход. Ако масивът е почти / напълно сортиран и ако изберем най-десния елемент като звено, разделянето на левия и десния подмасив ще бъде силно неравномерно.

Този метод предполага избор на началния шарнирен елемент по случаен начин. Не е нужно обаче да променяме логиката на разделяне.

Вместо да извикаме дял , ние извикваме метода randomPartition , който избира произволен елемент и го разменя с най-десния елемент, преди най-накрая да извика метода на дяла .

Нека внедрим метода 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) .

Обсъдихме и две вариации на Quick Select. Този алгоритъм не е ясен, но има времева сложност от O (n) в средни случаи.

Както винаги, пълният код на алгоритъма може да бъде намерен в GitHub.