src/main/java/com/thealgorithms/datastructures/heaps/KthElementFinder.java - master - NikolayIvkin/TheAlgorithms

src/main/java/com/thealgorithms/datastructures/heaps/KthElementFinder.java

59 строк2 KB

Hardik Pawar

Add KthElementFinder algorithm (#5836)

26 окт 2024, 12:30

26 окт 2024, 12:30d572997


package com.thealgorithms.datastructures.heaps;

import java.util.PriorityQueue;

/**
 * This class provides methods to find the Kth largest or Kth smallest element
 * in an array using heaps. It leverages a min-heap to find the Kth largest element
 * and a max-heap to find the Kth smallest element efficiently.
 *
 * @author Hardvan
 */
public final class KthElementFinder {
    private KthElementFinder() {
    }

    /**
     * Finds the Kth largest element in the given array.
     * Uses a min-heap of size K to track the largest K elements.
     *
     * Time Complexity: O(n * log(k)), where n is the size of the input array.
     * Space Complexity: O(k), as we maintain a heap of size K.
     *
     * @param nums the input array of integers
     * @param k the desired Kth position (1-indexed, i.e., 1 means the largest element)
     * @return the Kth largest element in the array
     */
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }

    /**
     * Finds the Kth smallest element in the given array.
     * Uses a max-heap of size K to track the smallest K elements.
     *
     * Time Complexity: O(n * log(k)), where n is the size of the input array.
     * Space Complexity: O(k), as we maintain a heap of size K.
     *
     * @param nums the input array of integers
     * @param k the desired Kth position (1-indexed, i.e., 1 means the smallest element)
     * @return the Kth smallest element in the array
     */
    public static int findKthSmallest(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        for (int num : nums) {
            maxHeap.offer(num);
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }
        return maxHeap.peek();
    }
}