Untitled

 avatar
unknown
plain_text
21 days ago
1.9 kB
1
Indexable
import java.util.*;

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

        // Step 2: Use a min-heap to keep track of top k frequent words
        PriorityQueue<String> minHeap = new PriorityQueue<>((word1, word2) -> {
            int freq1 = frequencyMap.get(word1);
            int freq2 = frequencyMap.get(word2);

            if (freq1 == freq2) {
                return word2.compareTo(word1); // Lexicographical order (reverse)
            }
            return freq1 - freq2; // Compare by frequency
        });

        for (String word : frequencyMap.keySet()) {
            minHeap.offer(word);
            if (minHeap.size() > k) {
                minHeap.poll(); // Remove the least frequent or lexicographically largest
            }
        }

        // Step 3: Extract words from the heap and sort them
        List<String> result = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            result.add(minHeap.poll());
        }
        Collections.reverse(result); // Reverse to get descending order
        return result;
    }

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

        // Example 1
        String[] words1 = {"i", "love", "leetcode", "i", "love", "coding"};
        int k1 = 2;
        System.out.println(solution.topKFrequent(words1, k1)); // Output: ["i", "love"]

        // Example 2
        String[] words2 = {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
        int k2 = 4;
        System.out.println(solution.topKFrequent(words2, k2)); // Output: ["the", "is", "sunny", "day"]
    }
}
Editor is loading...
Leave a Comment