Untitled
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