NC88 寻找第K大
算法知识视频讲解
中等 通过率：26.47% 时间限制：3秒 空间限制：64M
知识点
堆
分治
题目
题解(62)
讨论(255)
排行
描述
有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。

给定一个整数数组a,同时给定它的大小n和要找的K(1<=K<=n)，请返回第K大的数(包括重复的元素，不用去重)，保证答案存在。

示例1
输入：
[1,3,5,2,2],5,3
复制
返回值：
2
复制
示例2
输入：
[10,10,9,9,8,7,5,6,4,3,4,2],12,3
复制
返回值：
9
复制
说明：
去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9
关联企业
关联职位

思路和心得：

1.习惯上，先转化成第 （n + 1 - K）小。

2.快排
快排有3种写法。这里采用严版教材写法，左右挖坑互填

python3 代码

# -*- coding:utf-8 -*-

class Solution:
    def findKth(self, a, n, K):
        # write code here
        kmin = n + 1 - K
        self.quick_sort(a, 0, n - 1, kmin)
        return a[kmin - 1]

    #--------------------------- 手撸快排（左右交换法） -----------------------#
    def quick_sort(self, nums, lo: int, hi: int, k: int) -> None:
        if lo < hi:
            pivot_pos = self.partition(nums, lo, hi)
            cur_left_len = pivot_pos - lo + 1       #当前左侧的元素个数
            if  cur_left_len < k:
                self.quick_sort(nums, pivot_pos + 1, hi, k - cur_left_len)
            elif cur_left_len > k:
                self.quick_sort(nums, lo, pivot_pos - 1, k)

    def partition(self, nums, lo: int, hi: int) -> int:
        #--------------- 严版教材。挖坑法。左右交替，左右互填
        #-- 左边有坑
        pivot = nums[lo]
        #---- 左挖坑，右填。右挖坑，左填
        while lo < hi:
            #-- 此时左边有坑，需要找右边第一个不合理的位置去填
            while lo < hi and pivot <= nums[hi]:
                hi -= 1
            nums[lo] = nums[hi]
            #-- 此时右边有坑，需要找左边第一个不合理的位置去填
            while lo < hi and nums[lo] <= pivot:
                lo += 1
            nums[hi] = nums[lo]
        #-- 填补最初的坑
        nums[lo] = pivot
        return lo

也可以就按照第K大。看个人习惯

c++ 代码

class Solution {
public:
    int findKth(vector<int> a, int n, int K) 
    {
        // write code here

        quick_sort(a, 0,  n - 1, K);
        return a[n - K];
    }


    //---------------------- 严版左右挖坑互填 ----------------------//
    void quick_sort(vector<int> & nums, int lo, int hi, int k)
    {
        if (lo < hi)
        {
            int pivot_pos = partition(nums, lo, hi);
            int cur_right_len = hi - pivot_pos + 1;
            if (cur_right_len > k)
                quick_sort(nums,  pivot_pos + 1, hi, k);
            else if  (cur_right_len <  k)
                quick_sort(nums, lo, pivot_pos - 1, k - cur_right_len);
        }
    }

    int partition(vector<int> & nums, int lo, int hi)
    {
        int pivot = nums[lo];
        while (lo < hi)
        {
            while(lo < hi && pivot <= nums[hi])
                hi --;
            nums[lo] = nums[hi];
            while (lo < hi && nums[lo] <= pivot)
                lo ++;
            nums[hi] = nums[lo];
        }
        nums[lo] = pivot;
        return lo;
    }
};

java 代码

import java.util.*;

public class Solution 
{
    public int findKth(int[] a, int n, int K) 
    {
        // write code here
        int kmin = n + 1 - K;
        quick_sort(a, 0, n - 1, kmin);
        return a[kmin - 1];
    }

    public void quick_sort(int [] nums, int lo, int hi, int k)
    {
        if (lo < hi)
        {
            int pivot_pos = partition(nums, lo, hi);
            int cur_left_len = pivot_pos - lo + 1;
            if (cur_left_len < k)
                quick_sort(nums, pivot_pos + 1, hi, k - cur_left_len);
            else if (cur_left_len > k)
                quick_sort(nums, lo, pivot_pos - 1, k);
        }
    }

    public int partition(int [] nums, int lo, int hi)
    {
        int pivot = nums[lo];
        while (lo < hi)
        {
            while (lo < hi && nums[hi] >= pivot)    hi --;
            nums[lo] = nums[hi];
            while (lo < hi && nums[lo] <= pivot)    lo ++;
            nums[hi] = nums[lo];
        }
        nums[lo] = pivot;
        return lo;
    }

}