Sort an Array -3

題目：215. Kth Largest Element in an Array

連結：https://leetcode.com/problems/kth-largest-element-in-an-array/

• 等級：Medium

解題思路

1. minheap
2. 將所有元素放入heap中
3. 當heap空間大小大於K，移除root元素
4. 最後剩下K個最大元素，其中root為第K個最大元素。

class Solution {
    public int findKthLargest(int[] nums, int k) {
            PriorityQueue<Integer> heap = new PriorityQueue();

        //iterate over the array
        for (int n : nums) {
            //first add the integer to heap
            heap.add(n);
            //if size of the heap is greater than k
            if (heap.size() > k) {
                //remove the root element (lowest of all)
                heap.poll();
            }
        }
        //finally heap has k largest elements left with root as the kth largest element
        return heap.peek();
    }
}

• Time complexity: O(n*log ( k ))
• Space complexity: O(k)

題目：75. Sort Colors

連結：https://leetcode.com/problems/kth-largest-element-in-an-array/

• 等級：Medium

解題思路

1. 題目特殊數值只有012
2. 計算排序次數直接寫入

class Solution {
    public void sortColors(int[] nums) {
        int num0 = 0 ; 
        int num1 = 0 ;
        int num2 = 0 ; 
        for(int num : nums ){
            if (num == 0 ){
                num0++ ; 
            }
            if (num == 1 ){
                num1++ ; 
            }
            if (num == 2 ){
                num2++ ; 
            }
        }
       
        int i = 0 ; 
        while ( num0 > 0){
            nums[i++] = 0 ; 
            num0-- ; 
        }
        while ( num1 > 0){
            nums[i++] = 1; 
            num1-- ; 
        }
        while ( num2 > 0){
            nums[i++] = 2 ; 
            num2-- ; 
        }
    }
}

• Time complexity: O(n)
• Space complexity: O(1)