Reference: Link

We can use heapsort and quick select to find the kth element in array and top k elements.

215. Kth Largest Element in an Array (Medium)

There are three ways to solve this problem. Here is the link.

  1. Sort. We can just sort the array and find the kth element. Time complexity O(nlogn). Space complexity O(1).

     public int findKthLargest(int[] nums, int k) {
     Arrays.sort(nums);
     return nums[nums.length-k];
 }

  2. We can also use heap to solve this problem. In java, we use PriorityQueue to maintain our min-heap. The size of heap is k. We iterate the input array. If we find the size of min-heap is larger than k, we pop the minimum value. After iteration, the top value is the answer. Time complexity is O(nlogk). Space complexity is O(k).

     public int findKthLargest(int[] nums, int k) {
     PriorityQueue<Integer> heap = new PriorityQueue<>();
     for(int num:nums){
         heap.add(num);
         if(heap.size()>k)
             heap.poll();
     }
     return heap.peek();
 }

  3. We can use quick select to solve this problem. We don’t need to sort the whole array. We just need to know the kth element, so we can use quick select. At first, we find a pivot. And calculate the number of elements which are larger than this pivot. Then, we know whether this pivot is the kth element. Time complexity is O(n). Space complexity is O(1).

     public int findKthLargest(int[] nums, int k) {
     int left = 0;
     int right = nums.length-1;
     while(true){
         int index = partition(nums,left,right);
         if(index == k-1)return nums[index];
         else if(index<k-1)left = index+1;
         else right = index-1;
     }
 }
    
 public int partition(int[]nums,int left,int right){
     int pivot = left;
     int l = left+1,r = right;
     while(l<=r){
         if(nums[l]<nums[pivot] && nums[r]>nums[pivot]){
             int temp = nums[l];
             nums[l]=nums[r];
             nums[r] = temp;
             r--;
             l++;
         }
         else if(nums[l]>=nums[pivot])l++;
         else if(nums[r]<=nums[pivot])r--;
     }
     int temp = nums[pivot];
     nums[pivot]=nums[r];
     nums[r] = temp;
     return r;
 }

347. Top K Frequent Elements (Medium)

We need to use min-heap to solve this problem. We store k most frequent elements in our heap. In order to achieve this solution. We need HashMap and PriorityQueue in Java. The key of hashmap is number, the value is the frequency of this number. And we need to design our min-heap according to the frequency of these numbers. Then we try to store all elements in min-heap and ensure the size is always k. Here is the link

Time complexity is O(nlogk). Space complexity is O(n).

    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer>map = new HashMap();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>((n1, n2) -> map.get(n1) - map.get(n2));
        
        for(int key:map.keySet()){
            queue.add(key);
            if(queue.size()>k)
                queue.poll();
        }
        
        int []ans = new int[k];
        for(int i =0;i<k;i++){
            ans[i] = queue.poll();
        }
        return ans;
    }

451. Sort Characters By Frequency (Medium)

This problem is exactly same as the last problem. You can use the same way to solve it. Here is the link.

Time complexity is O(nlogn). Space complexity is O(n).

    public String frequencySort(String s) {
        HashMap<Character,Integer>map = new HashMap();
        for(int i =0;i<s.length();i++){
            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
        }
        
        PriorityQueue<Character> queue = new PriorityQueue((n1,n2) -> map.get(n1)-map.get(n2));
        for(Character key:map.keySet()){
            queue.add(key);
        }
        String ans = "";
        while(!queue.isEmpty()){
            Character str = queue.poll();
            int times = map.get(str);
            for(int i =0;i<times;i++){
                ans = String.valueOf(str) + ans;
            }
        }
        return ans;
    }

Summary

From these problems, we find if we need to calculate the kth element in array/string, or find first k elements in array/string, we can use quick select and heasort to solve this kind of problems.