Согласно этой статье Нахождение K-го по величине элемента в списке из n элементов следующий алгоритм займет O(n) время в худшем случае.
- Разделите массив на n / 5 списков по 5 элементов в каждом.
- Найдите медиану в каждом подмассиве из 5 элементов.
- Рекурсивно найти медиану всех медиан, назовем это M
- Разделение массива на два подмассива. 1-й подмассив содержит элементы больше, чем M, допустим, что этот подмассив имеет значение a1, а другой подмассив содержит элементы, меньшие M. a2.
- Если k <= | a1 |, вернуть выбор (a1, k). </li>
- Если k− 1 = | a1 |, вернуть M.
- Если k> | a1 | + 1, возврат выбора (a2, k −a1 - 1).
Анализ: Как указано в оригинальной статье:
Мы используем медиану для разбиения списка на две половины (первая половина,
если k <= n/2, а во второй половине иначе). Этот алгоритм занимает
время cn на первом уровне рекурсии для некоторой константы c, cn/2 при
следующий уровень (поскольку мы повторяем в списке размером n / 2), cn/4 на
третий уровень и тд. Общее время заняло cn + cn/2 + cn/4 +
.... = 2cn = o(n).
Почему размер раздела взят 5, а не 3?
Как указано в оригинальной бумаге :
Разделение списка на 5 обеспечивает наихудшее разделение на 70 - 30. Atleast
половина медиан, превышающих медиану медиан, следовательно, по крайней мере
половина блоков n / 5 имеет по крайней мере 3 элемента, и это дает
3n/10 split, что означает, что другой раздел равен 7n / 10 в худшем случае.
Это дает T(n) = T(n/5)+T(7n/10)+O(n). Since n/5+7n/10 < 1,
наихудшее время работы - O(n).
Теперь я попытался реализовать приведенный выше алгоритм как:
public static int findKthLargestUsingMedian(Integer[] array, int k) {
// Step 1: Divide the list into n/5 lists of 5 element each.
int noOfRequiredLists = (int) Math.ceil(array.length / 5.0);
// Step 2: Find pivotal element aka median of medians.
int medianOfMedian = findMedianOfMedians(array, noOfRequiredLists);
//Now we need two lists split using medianOfMedian as pivot. All elements in list listOne will be grater than medianOfMedian and listTwo will have elements lesser than medianOfMedian.
List<Integer> listWithGreaterNumbers = new ArrayList<>(); // elements greater than medianOfMedian
List<Integer> listWithSmallerNumbers = new ArrayList<>(); // elements less than medianOfMedian
for (Integer element : array) {
if (element < medianOfMedian) {
listWithSmallerNumbers.add(element);
} else if (element > medianOfMedian) {
listWithGreaterNumbers.add(element);
}
}
// Next step.
if (k <= listWithGreaterNumbers.size()) return findKthLargestUsingMedian((Integer[]) listWithGreaterNumbers.toArray(new Integer[listWithGreaterNumbers.size()]), k);
else if ((k - 1) == listWithGreaterNumbers.size()) return medianOfMedian;
else if (k > (listWithGreaterNumbers.size() + 1)) return findKthLargestUsingMedian((Integer[]) listWithSmallerNumbers.toArray(new Integer[listWithSmallerNumbers.size()]), k-listWithGreaterNumbers.size()-1);
return -1;
}
public static int findMedianOfMedians(Integer[] mainList, int noOfRequiredLists) {
int[] medians = new int[noOfRequiredLists];
for (int count = 0; count < noOfRequiredLists; count++) {
int startOfPartialArray = 5 * count;
int endOfPartialArray = startOfPartialArray + 5;
Integer[] partialArray = Arrays.copyOfRange((Integer[]) mainList, startOfPartialArray, endOfPartialArray);
// Step 2: Find median of each of these sublists.
int medianIndex = partialArray.length/2;
medians[count] = partialArray[medianIndex];
}
// Step 3: Find median of the medians.
return medians[medians.length / 2];
}
Просто ради завершения, другой алгоритм использует очередь приоритетов и занимает время O(nlogn).
public static int findKthLargestUsingPriorityQueue(Integer[] nums, int k) {
int p = 0;
int numElements = nums.length;
// create priority queue where all the elements of nums will be stored
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
// place all the elements of the array to this priority queue
for (int n : nums) {
pq.add(n);
}
// extract the kth largest element
while (numElements - k + 1 > 0) {
p = pq.poll();
k++;
}
return p;
}
Оба эти алгоритма могут быть протестированы как:
public static void main(String[] args) throws IOException {
Integer[] numbers = new Integer[]{2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};
System.out.println(findKthLargestUsingMedian(numbers, 8));
System.out.println(findKthLargestUsingPriorityQueue(numbers, 8));
}
Ожидаемый результат:
18
18