Sponsored
Sponsored
By using a Min-Heap, we can efficiently keep track of the k largest elements. Maintain a heap of size k, and for each element in the array, decide whether to add it to the heap. If you add an element to the heap when it is full, remove the minimum element to maintain the size of the heap as k. At the end, the root of the heap will be the kth largest element.
Time Complexity: O(n log n), where n is the size of the array, because of the sorting operation.
Space Complexity: O(1), as we are modifying the input array in-place.
1import heapq
2
3def findKthLargest(nums, k):
4 minHeap = []
5 for num in nums:
6 heapq.heappush(minHeap, num)
7 if len(minHeap) > k:
8 heapq.heappop(minHeap)
9 return minHeap[0]
10
11nums = [3,2,1,5,6,4]
12k = 2
13print(findKthLargest(nums, k))We use Python's heapq module to maintain a min-heap. For each element in the array, the element is pushed to the heap. If the heap size exceeds k, the smallest element is popped. The smallest element remaining in the heap is the kth largest element.
Quickselect is an efficient selection algorithm to find the kth smallest element in an unordered list. The algorithm is related to the quicksort sorting algorithm. It works by partitioning the data, similar to the partitioning step of quicksort, and is based on the idea of reducing the problem size through partitioning.
Average-case Time Complexity: O(n), but worst-case O(n²).
Space Complexity: O(1) for iterative solution, O(log n) for recursive calls due to stack depth.
1using System;
class KthLargestElement {
private static int Partition(int[] nums, int left, int right, int pivotIndex) {
int pivotValue = nums[pivotIndex];
Swap(ref nums[pivotIndex], ref nums[right]);
int newPivotIndex = left;
for (int i = left; i < right; i++) {
if (nums[i] > pivotValue) {
Swap(ref nums[newPivotIndex++], ref nums[i]);
}
}
Swap(ref nums[newPivotIndex], ref nums[right]);
return newPivotIndex;
}
private static void Swap(ref int a, ref int b) {
int temp = a;
a = b;
b = temp;
}
private static int QuickSelect(int[] nums, int left, int right, int k) {
if (left == right) return nums[left];
Random rand = new Random();
int pivotIndex = rand.Next(left, right + 1);
pivotIndex = Partition(nums, left, right, pivotIndex);
if (pivotIndex == k) return nums[k];
else if (pivotIndex < k) return QuickSelect(nums, pivotIndex + 1, right, k);
else return QuickSelect(nums, left, pivotIndex - 1, k);
}
public static int FindKthLargest(int[] nums, int k) {
return QuickSelect(nums, 0, nums.Length - 1, k - 1);
}
static void Main() {
int[] nums = {3,2,1,5,6,4};
int k = 2;
Console.WriteLine(FindKthLargest(nums, k));
}
}The explained C# solution employs recursive logic through a randomized Quickselect setup aiming at secure partitioning against degenerative pivot dictation. Messaged swaps ensure relative positions provide shrink search domains between elimination.