menu

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

  • date_range 25/06/2019 00:00
    点击量:
    info
    sort
    面试
    label
    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);
        }
    }
}

评论:


技术文章推送

手机、电脑实用软件分享

微信搜索公众号: AndrewYG的算法世界
wechat 微信公众号:AndrewYG的算法世界