20210126.md

Algorithm

215. Kth Largest Element in an Array

Description

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:

• You may assume k is always valid, 1 ≤ k ≤ array's length.

Solution

快速排序

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length, low = 0, high = n-1;
        while(low<=high){
            int x = partition(nums, low, high);
            if(x == n-k){
                return nums[x];
            }else if(x < n-k){
                low = x+1;
            }else{
                high = x-1;
            }
        }
        return low;
    }

    private int partition(int[] nums, int low, int high){
        int i = low;
        int j = high;
        int pivot = nums[i];
        while(i<j){
            while(i<j && pivot<nums[j]){
                j--;
            }
            if(i<j){
                nums[i] = nums[j];
                nums[j] = pivot;
                i++;
            }
            while(i<j && pivot>nums[i]){
                i++;
            }
            if(i<j){
                nums[j] = nums[i];
                nums[i] = pivot;
                j--;
            }
        }
        return i;
    }
}

最大堆

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        for(int item:nums) {
            minHeap.offer(item);
            if(minHeap.size()>k) {
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }
}

class Solution {
    private int size=0;
    public int findKthLargest(int[] nums, int k) {
        size = nums.length;

        heapify(nums);

        for(int i=0; i<k-1; i++)
            delete(nums);
        return nums[0];
    }

    void heapify(int[] nums){
        for(int i=size/2 -1; i>=0; i--){
            percolateDown(nums, i);
        }
    }

    void delete(int nums[]){
        nums[0] = nums[size-1];
        size--;
        percolateDown(nums, 0);
    }

    void percolateDown(int nums[], int index){
        while(index < size){
            int max = index;
            if(getLeft(index) != -1 && nums[getLeft(index)] > nums[max])
                max = getLeft(index);
            if(getRight(index) != -1 && nums[getRight(index)] > nums[max])
                max = getRight(index);

            if(max != index){
                swap(max, index, nums);
                index = max;
            }
            else break;
        }
    }
    void swap(int indexA, int indexB, int arr[]){
        int temp = arr[indexB];
        arr[indexB] = arr[indexA];
        arr[indexA] = temp;
    }
    int getLeft(int index){
        return (index*2 + 1) >= size ? -1 : (index*2 + 1);
    }
    int getRight(int index){
        return (index*2 + 2) >= size ? -1 : (index*2 + 2);
    }
}

Discuss

借助快速排序的思想

Review

Tip

Share