top-k-frequent-words.dart (1645B)
1 //Given a list of words return the k most frequently used 2 //words in the list. If there are multiple words used the same 3 //number of times return them in lexographical order. 4 //To do this I first created a map that stored how many times 5 //a given word was used. Then from there I created a sorted list 6 //that stored the number of times each word was used and sorted it. 7 //I then created a list for each number of occurences meaning 8 //if a word occurs twice then there should be two lists one for 9 //words that happen one time and one for words that happen twice. 10 //Then I iterated through these lists to find the most common elements. 11 //Time: 305ms Beats: 47.6% 12 //Memory: 145MB Beats: 70.59% 13 class Solution { 14 List<String> topKFrequent(List<String> words, int k) { 15 Map<String,int> vals = {}; 16 for(int i = 0 ; i < words.length ; ++i){ 17 vals[words[i]] = (vals[words[i]] ?? 0) + 1; 18 } 19 List<int> usages = []; 20 for(var entry in vals.entries){ 21 usages.add(entry.value); 22 } 23 usages.sort(); 24 List<String> return_list = []; 25 int distinct = usages[usages.length - 1] - usages[0]; 26 int offset = usages[0]; 27 List<List<String>> lists = []; 28 for(int i = 0 ; i <= distinct ; ++i){ 29 lists.add([]); 30 } 31 for(var entry in vals.entries){ 32 lists[entry.value - offset].add(entry.key); 33 } 34 for(int i = lists.length - 1; i >= 0 && return_list.length < k; --i){ 35 lists[i].sort(); 36 for(int x = 0 ; x < lists[i].length && return_list.length < k ; ++x){ 37 return_list.add(lists[i][x]); 38 } 39 } 40 return return_list; 41 } 42 }