算法-数组-快速排序-第k大个数

25/06/2019 00:00

点击量：次

面试

java

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

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.

快排的每一次排序就是找到一个第N大的数，修改快排的递归逻辑。算法复杂度为O(N)。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return sort(nums, 0, nums.length-1, k);
    }
    
    private int sort(int[] nums, int left, int right, int k){
        int base = nums[left];
        int leftt = left;
        int rightt = right;
        while(leftt < rightt){
            while(leftt < rightt && nums[rightt] > base){
                rightt--;
            }
            if(leftt < rightt){
                int temp = nums[rightt];
                nums[rightt] = nums[leftt];
                nums[leftt] = temp;
                leftt++;
            }
            while(leftt < rightt && nums[leftt] < base){
                leftt++;
            }
            if(leftt < rightt){
                int temp = nums[rightt];
                nums[rightt] = nums[leftt];
                nums[leftt] = temp;
                rightt--;
            }
        }
         int rank = nums.length - leftt;
        if(rank == k){
            return nums[leftt];
        }else if(rank<k){
            return sort(nums, left, leftt-1, k);
        }else{
            return sort(nums, leftt+1, right, k);
        }
    }
}

算法-数组-快速排序-第k大个数

评论：