快排求第k大的数

超、凢脫俗 2022-11-30 15:42 132阅读 0赞

思路就是快排结合第k大。  
注意两个点：一，你排序的时候，是从小到大地排序，所以如果是找倒数第k大的数字的话，应该返回的是倒数的第k个，就需要转换成n-k 个  
注意第二个点：在设置进入判断的时候，需要让l<=r 的时候进入判断。因为如果到了最左或者左右边，也需要进入。

code

#include <bits/stdc++.h>
    using namespace std;
    //错在了我的排序是顺序增长的，要看第k大应该是用 low==n-k
    void quick(vector<int> &nums, int l, int r, int k,int &res){ 
        if(l<=r){        //相等的情况
            int sentry=nums[l],low=l,high=r;
            while(low<high){ 
                while(high>low && nums[high]>sentry)
                    high--;
                if(high>low)
                    nums[low++]=nums[high];
                while(high>low && nums[low]<sentry)
                    low++;
                if(high>low)
                    nums[high--]=nums[low];
            }
            nums[low]=sentry;
            if(low==nums.size()-k){        //错误再此
               // cout<<low<<endl;
                res=sentry;
                return ;
            }
                
            quick(nums,l,low-1,k,res);
            quick(nums,low+1,r,k,res);
            return ;
        }
        return ;
    }
    
    
        int findKth(vector<int> a, int n, int K) { 
            // write code here
            int res=0;
        quick(a,0,n-1,K,res);
        return res;
        }
        
    
    int main() { 
        vector<int> test={ 1,3,5,2,23,432,6,23,9,8,8,7};
        int k=4;
        int res=findKth(test,test.size(),k);
        cout<<res<<endl;
        getchar();
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，132人围观）

还没有评论，来说两句吧...

相关阅读

相关快排找出第K大的数（C++实现）

算法实现： include <stdio.h> void printAll(int a[], int n){ int

蔚落/ 2024年03月16日 14:46/ 0 赞/ 10 阅读

相关寻找第 K 大的数

寻找第 K 大的数 1、参考资料 https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

爱被打了一巴掌/ 2022年12月05日 04:51/ 0 赞/ 185 阅读

相关快排求第k大的数

思路就是快排结合第k大。注意两个点：一，你排序的时候，是从小到大地排序，所以如果是找倒数第k大的数字的话，应该返回的是倒数的第k个，就需要转换成n-k 个注意第二个

超、凢脫俗/ 2022年11月30日 15:42/ 0 赞/ 133 阅读

相关使用快排一次划分求第k小、使用优先级队列、使用堆

快排 include <iostream> using namespace std; / Partition() 快排

落日映苍穹つ/ 2022年11月11日 14:59/ 0 赞/ 102 阅读

相关求一个数组中第k大的数方法

求一个数组中第k大的数，我第一印象是冒泡，因为只要冒泡k趟即可，第一趟冒泡第一大，第二次冒泡第二大，第k次冒泡第k大，时间复杂度为O(kn),n为数组长度。但是我们都知道快速排

忘是亡心i/ 2022年09月26日 02:24/ 0 赞/ 134 阅读

相关算法题目——第K大的数

题目链接：[剑指offer.76][offer.76] 思路：使用 priority\_queue 构建优先队列，这里注意要构建大顶堆，使less； pop() 弹

Myth丶恋晨/ 2022年09月15日 12:45/ 0 赞/ 119 阅读

相关【数字之魅】寻找最大的K个数(求第k大的数)

前言：编程之美上并没有给出实际的代码，这里我参考yoona博主的做法自己也写了一遍，并记录下来。与此相似的题目是： \- 求第k大的数 \- 求第k小的数这

悠悠/ 2022年08月09日 05:14/ 0 赞/ 152 阅读

相关求前K小的数和第K小的数

求前K小的数和第K小的数 1. 前K小的数（堆排序实现） include<iostream> include<algorithm> inclu

落日映苍穹つ/ 2022年08月06日 13:19/ 0 赞/ 139 阅读

相关寻找第K大的数

1，对于一个有序数组则为第K个数，O（1） 2，对于一个无序数组使用修改的快排划分算法，时间复杂度为O（n） 3，对于两个无序数组

小咪咪/ 2022年05月21日 03:20/ 0 赞/ 142 阅读

相关 [数据结构][Python][经典题目]无序序列中第k大的数引申快排

def partition(seq): pi, seq, = seq[0],seq[1:] lo = [x for x in seq i

客官°小女子只卖身不卖艺/ 2022年01月23日 01:21/ 0 赞/ 181 阅读