Some Points on Priority queue
---------------------------------------
1)Since a priority queue needs to compare its elements and order them accordingly, the user defined class must implement the Comparable interface, or you must provide a Comparator while creating the priority queue. Otherwise, the priority queue will throw a ClassCastException when you add new objects to it.(https://www.callicoder.com/java-priority-queue/)
2)By default all wrapper class implement comparable interface
Leet Code problem 347. Top K Frequent Elements
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Solution we are going to use HashMap , Priority queue and Array
package LeetCode;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Queue;
public class TopKElements {
public int[] topKEmements(int[] nums, int k) {
HashMap<Integer, Integer> cache = new HashMap<>();
for (int num : nums) {
cache.put(num, cache.getOrDefault(num, 0) + 1);
}
Queue<Integer> minHeap = new PriorityQueue<>((a, b) -> cache.get(a) - cache.get(b));// Comparator so that it
// gets stored in the order
// where least occured
// element is stored in the
// top
for (int num : cache.keySet()) {
minHeap.add(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
int[] arr = new int[k];
int index = 0;
while (minHeap.size() != 0) {
int val = minHeap.poll();
arr[index++] = val;
}
return arr;
}
public static void main(String[] args) {
TopKElements elements = new TopKElements();
int[] nums = { 1, 1, 1, 2, 2, 3 };
int[] result = elements.topKEmements(nums, 2);
for (int number : result) {
System.out.println("Result is " + number);
}
}
}
Kth larets element in an array
Formula could be (length of array - k) this will give the index of the kth largest element
For example [ 2 1 3 8 9] is the array k =2 that means finf 2nd largest
Step 1: Sort the array [1 2 3 8 9]
step 2:length of array - k --> (5 -2) which is 3 i.e at 3rd index we have 2nd largets element
Similarlly 3rd largets means
5-3 which is 2 i.e at 2nd index we have 3rd largest element in the array
Using priority queue approach
----------------------------------------
1)Insert elements in to priority queue which will be inserted in to default ordering i.e least element will be removed first when we poll
2)We poll from queue when size becomes grater than k
that where we get result
Following is the code
package LeetCode;
import java.util.Arrays;
import java.util.PriorityQueue;
public class KthLargetsElement {
public int findkthLatgestUsingBruteForce(int[] numbers, int k) {
Arrays.sort(numbers);
int kthIndex = numbers.length - k;
return numbers[kthIndex];
}
public int findkthLargestUsingPriorityQueue(int[] numbers, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : numbers) {
pq.offer(num);
if (pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}
public static void main(String[] args) {
KthLargetsElement element = new KthLargetsElement();
int[] numbers = { 102 ,6,100,500,78 };
int k = 2;
int result = element.findkthLatgestUsingBruteForce(numbers, k);
System.out.println(k + "th largest element is " + result);
int resultUsingPriorityQueue = element.findkthLargestUsingPriorityQueue(numbers, k);
System.out.println("Result using priority queue " + resultUsingPriorityQueue);
}
}
String program Group Annagrams
----------------------------------------------
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class GroupAnnagrams {
public List<String> groupAnagrams(String[] strs) {
// base case
if (strs.length == 0 || strs == null)
return new ArrayList<String>();
Map<String, List<String>> map = new HashMap<>();
for (String word : strs) {
// convert every string to a char array
char[] ch = word.toCharArray();
// sorted the array, this is easy for this logic to determine whether a key
// repeats or not
Arrays.sort(ch);
String sortedStr = String.valueOf(ch);
// if the hash map does not contain the sorted key in a given loop then we add
// it to the
// hash map along with a new ArrayList<String>() value
if (!map.containsKey(sortedStr))
map.put(sortedStr, new ArrayList<String>());
// we keep adding values to a list for a key in existing loop
map.get(sortedStr).add(word);
}
// return the group by iterating over all the values in the hash map and pass
// them to the constructor
// return new ArrayList<List<String>>(map.values());
return new ArrayList(map.values());
}
public static void main(String[] args) {
GroupAnnagrams grp = new GroupAnnagrams();
String[] strs = {"eat","tea","tan","ate","nat","bat"};
//String[] strs = { "" };
System.out.println("Annagrams are " + grp.groupAnagrams(strs));
}
}
