Untitled

import java.util.*;

public class TopKFrequentQuickSelect {
    public int[] topKFrequent(int[] nums, int k) {
        // Step 1: Build frequency map
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Step 2: Convert frequency map to a list of pairs [num, freq]
        List<int[]> freqList = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            freqList.add(new int[]{entry.getKey(), entry.getValue()});
        }

        // Step 3: Use QuickSelect to partition the list around the (n-k)th most frequent element
        int n = freqList.size();
        quickSelect(freqList, 0, n - 1, n - k);

        // Step 4: Extract the top k elements (last k elements in the list)
        int[] result = new int[k];
        for (int i = n - k, j = 0; i < n; i++, j++) {
            result[j] = freqList.get(i)[0];
        }
        return result;
    }

    private void quickSelect(List<int[]> freqList, int left, int right, int targetIndex) {
        Random random = new Random();

        while (left <= right) {
            // Pick a random pivot and partition the list
            int pivotIndex = left + random.nextInt(right - left + 1);
            int partitionIndex = partition(freqList, left, right, pivotIndex);

            if (partitionIndex == targetIndex) {
                return; // Target index is correctly positioned
            } else if (partitionIndex < targetIndex) {
                left = partitionIndex + 1; // Look on the right side
            } else {
                right = partitionIndex - 1; // Look on the left side
            }
        }
    }

    private int partition(List<int[]> freqList, int left, int right, int pivotIndex) {
        int[] pivot = freqList.get(pivotIndex);
        int pivotFreq = pivot[1];

        // Move pivot to the end
        Collections.swap(freqList, pivotIndex, right);

        int storeIndex = left;
        for (int i = left; i < right; i++) {
            // Higher frequency elements go to the left
            if (freqList.get(i)[1] > pivotFreq) {
                Collections.swap(freqList, storeIndex, i);
                storeIndex++;
            }
        }

        // Move pivot to its correct position
        Collections.swap(freqList, storeIndex, right);
        return storeIndex;
    }

    public static void main(String[] args) {
        TopKFrequentQuickSelect solution = new TopKFrequentQuickSelect();

        // Example 1
        int[] nums1 = {1, 1, 1, 2, 2, 3};
        int k1 = 2;
        System.out.println(Arrays.toString(solution.topKFrequent(nums1, k1))); // Output: [1, 2]

        // Example 2
        int[] nums2 = {1};
        int k2 = 1;
        System.out.println(Arrays.toString(solution.topKFrequent(nums2, k2))); // Output: [1]
    }
}