public static List<String> topK(int k, Iterator<String> iter) {
PriorityQueue<String> miniHeap = new PriorityQueue<>(k, new Comparator<String>(){
@Override
public int compare(String s1, String s2){
return Integer.compare(s1.length(), s2.length());
}
});
while(iter.hasNext()){
String s = iter.next();
if (s.length() > miniHeap.peek().length()) {
miniHeap.add(s);
}
}
return new ArrayList<>(miniHeap);
}
378 Kth Smallest Number in a Sorted Matrix
Find the kth smallest number in at row and column sorted matrix.
Pair class to store x and y index
Put numbers in first column or first row
Poll number and add new number based on previous row, loop k-1 times
class pair{
private int x, y, val;
public pair(int x, int y, int val){
this.x = x;
this.y = y;
this.val = val;
}
}
public int kthSmallest(int[][] matrix, int k) {
int m = matrix.length;
int n = matrix[0].length;
PriorityQueue<pair> minHeap = new PriorityQueue<>(m, (a, b) -> a.val - b.val);
// add numbers in first column
for(int i=0; i<m ;i++){
minHeap.add(new pair(i, 0, matrix[i][0]));
}
for(int i=0; i<k-1; i++){
pair min = minHeap.poll();
if(min.y == n-1) continue;
minHeap.add(new pair(min.x, min.y+1, matrix[min.x][min.y+1]));
}
return minHeap.peek().val;
}
373 Find K Pairs with Smallest Sums
You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
Define a pair (u,v) which consists of one element from the first array and one element from the second array.
Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.
Use a minHeap to store sum
Pull out the sum and put new sum based on previous nums1 + 1
def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
if not nums1 or not nums2: return []
m, n = len(nums1), len(nums2)
q = [(nums1[i]+nums2[0], i, 0) for i in range(m)]
heapify(q)
ans = []
for i in range(m*n):
s, p1, p2 = heappop(q)
ans.append([nums1[p1], nums2[p2]])
if len(ans) == k: break
if p2 == n-1: continue
heappush(q, (nums1[p1] + nums2[p2+1], p1, p2+1))
return ans
692 Top K frequent word
Order the words by the frequency of them in the return list, the most frequent one comes first. If two words has the same frequency, the one with lower alphabetical order come first.
PriorityQueue: put the String in reverse compareTo order if they have same frequency
Time O(nlogk)
public String[] topKFrequentWords(String[] words, int k) {
if (k == 0 || words == null || words.length == 0){
return new String[0];
}
Map<String, Integer> map = new HashMap<>();
for (String word : words){
map.put(word, map.getOrDefault(word, 0) + 1);
}
Comparator<String> cmp = new Comparator<String>(){
public int compare(String s1, String s2){
if (map.get(s1) == map.get(s2)){
return s2.compareTo(s1);
// alphabetical order in reverse order in minHeap
}else{
return map.get(s1) - map.get(s2);
}
}
};
Queue<String> minHeap = new PriorityQueue<>(k, cmp);
for (String word: map.keySet()){
minHeap.add(word);
if (minHeap.size() > k) minHeap.poll();
}
String[] ans = new String[k];
for (int i=k-1; i >=0; i--){
ans[i] = minHeap.poll();
}
Arrays.sort(ans);
return ans;
}
Bucket with list List[] bucket, bucket[i] is the frequency of string
Time avg O(nlogk), best O(klogk), worst O(nlogn)
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> map = new HashMap<String, Integer>();
for (String word:words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
int N = words.length + 1;
List<String>[] bucket = new List[N];
for (String key: map.keySet()){
int freq = map.get(key);
if (bucket[freq] == null)
bucket[freq] = new ArrayList<String>();
bucket[freq].add(key);
}
List<String> ret = new ArrayList<String>();
for (int i = N - 1; i >= 0 && ret.size() < k; i--) {
if (bucket[i] != null) {
Collections.sort(bucket[i]);
ret.addAll(bucket[i]);
}
}
return ((ArrayList)ret).subList(0, k);
}
Trie[] bucket, bucket[i] store the strings in same frequency
Time: O(n * avgLenOfWord)
1244. TopK Leaderboard
Design a Leaderboard class, which has 3 functions:
addScore(playerId, score): Update the leaderboard by adding score to the given player's score. If there is no player with such id in the leaderboard, add him to the leaderboard with the given score.
top(K): Return the score sum of the top K players.
reset(playerId): Reset the score of the player with the given id to 0 (in other words erase it from the leaderboard). It is guaranteed that the player was added to the leaderboard before calling this function.
O(nlogk)
class Leaderboard {
Map<Integer, Integer> map;
public Leaderboard() {
map = new HashMap<>();
}
public void addScore(int playerId, int score) {
map.put(playerId, map.getOrDefault(playerId, 0) + score);
}
public int top(int K) {
Queue<Integer> pq = new PriorityQueue<>();
for (int v: map.values()){
pq.add(v);
if (pq.size() > K){
pq.poll();
}
}
int sum = 0;
while (!pq.isEmpty()){
sum += pq.poll();
}
return sum;
}
public void reset(int playerId) {
map.put(playerId, 0);
}
}
O(KlogN)
class Leaderboard {
Map<Integer, Integer> map;
TreeMap<Integer, Integer> sorted;
public Leaderboard() {
map = new HashMap<>();
sorted = new TreeMap<>(Collections.reverseOrder());
}
// O(logN) remove on TreeMap
public void addScore(int playerId, int score) {
if (!map.containsKey(playerId)) {
map.put(playerId, score);
sorted.put(score, sorted.getOrDefault(score, 0) + 1);
} else {
int preScore = map.get(playerId);
sorted.put(preScore, sorted.get(preScore) - 1);
if (sorted.get(preScore) == 0) {
sorted.remove(preScore);
}
int newScore = preScore + score;
map.put(playerId, newScore);
sorted.put(newScore, sorted.getOrDefault(newScore, 0) + 1);
}
}
// O(KlogN) K times * get on TreeMap (logN)
public int top(int K) {
int sum = 0;
for (int key: sorted.keySet()){
int times = sorted.get(key);
for (int i=0; i < times; i++){
sum += key;
K-=1;
if (K == 0) break;
}
if (K == 0) break;
}
return sum;
}
// O(logN) remove on TreeMap
public void reset(int playerId) {
int preScore = map.get(playerId);
sorted.put(preScore, sorted.get(preScore) - 1);
if (sorted.get(preScore) == 0) {
sorted.remove(preScore);
}
map.remove(playerId);
}
}
