[matrix/leetcode](sort)Kth Largest Element in an Array-快速排序

迈不过友情╰ 2021-09-28 07:46 214阅读 0赞

### Kth Largest Element in an Array-快速排序 ###

*   *  前言
     *  题干
     *  代码

## 前言 ##

这道题当作是快速排序的一个模板了,主要要记住qsort的几个参数的含义

## 题干 ##

给定一个未排序的整型数组，有 n(2≤n≤105) 个元素，求第 k 大的元素。

请为下面的 Solution 类实现解决上述问题的函数 findKthLargest，函数返回值为向量 nums 中第 k 大的元素。

class Solution { 
    public:
        int findKthLargest(vector<int>& nums, int k) { 
    
        }
    };

例1: nums = \[3, 2, 1, 5, 6, 4\], k = 2, 函数返回 5.

例2: nums = \[3, 2, 3, 1, 2, 4, 5, 5, 6\], k=4, 函数返回 4.

注意：请不要使用库函数排序。你只需要提交 Solution 类的代码，你可以在本地可以编写 main 函数测试程序，但不需要提交 main 函数的代码，不要修改类和函数的名称。

## 代码 ##

#include<vector>
    #include<iostream>
    using namespace std;
    class Solution { 
    public:
    	
    	static void qsort(vector<int>& nums,int left,int right,int k){ 
    		int size=nums.size();
    		if(size<=0) return;
    		
    		int i=left;
    		int j=right;
    		int base=nums[left];
    		
    		while(i<j){ 
    			while(nums[j]<=base && i<j) j--;
    			
    			if(i<j) nums[i]=nums[j];
    			
    			while(nums[i]>=base && i<j) i++;
    			
    			if(i<j) nums[j]=nums[i];
    		} 
    		
    		nums[i]=base;
    		if(i+1>k) qsort(nums,left,i-1,k);
    		else if(i+1<k) qsort(nums,i+1,right,k);
    		else return;
    	}
    	
        int findKthLargest(vector<int>& nums, int k) { 
    		
    		qsort(nums,0,nums.size()-1,k);
    		
    		return nums[k-1];
        }
    };