网易2016 实习研发工程师 [编程题]寻找第K大 and leetcode 215. Kth Largest Element in an Array

传送门

有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。

给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

测试样例：

[1,3,5,2,2],5,3

返回：2

note:

注意手写快排的时候：

        while(i < j) {
            while(j > i && a[j] > a[left]) j--;
            while(i < j && a[i] <= a[left]) i++;
            if(i < j) {
                swap(a[i],a[j]);
            }
        }

while(j > i && a[j] > a[left]) j--;
while(i < j && a[i] <= a[left]) i++;

这两个顺序不能反了，不然下标会错位一个

class Finder {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        return quickfind(a,0,n - 1,K);
    }
    
    int quickfind(vector<int> &a,int left,int right,int K) {
        int i = left,j = right;
        while(i < j) {
            while(j > i && a[j] > a[left]) j--;
            while(i < j && a[i] <= a[left]) i++;
            if(i < j) {
                swap(a[i],a[j]);
            }
        }
        swap(a[left],a[i]);
        int dis = right - i + 1;
        if(dis == K){
            return a[i];
        }
        else if(K < dis) {
            return quickfind(a,i + 1,right,K);
        }
        else{
            return quickfind(a,left,i - 1 ,K - dis);
        }
    }
};

--------------------------------------------------

leetcode:

传送门

215. Kth Largest Element in an Array

 

QuestionEditorial Solution

 My Submissions

 

• Total Accepted: 67793
• Total Submissions: 195182
• Difficulty: Medium

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.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

Hide Tags

 Heap Divide and Conquer

Show Similar Problems

 

 

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickfind(nums,0,nums.size() - 1,k);
    }
    
    int quickfind(vector<int> &a,int left,int right,int K) {
        int i = left,j = right;
        while(i < j) {
            while(j > i && a[j] > a[left]) j--;
            while(i < j && a[i] <= a[left]) i++;
            if(i < j) {
                swap(a[i],a[j]);
            }
        }
        swap(a[left],a[i]);
        int dis = right - i + 1;
        if(dis == K){
            return a[i];
        }
        else if(K < dis) {
            return quickfind(a,i + 1,right,K);
        }
        else{
            return quickfind(a,left,i - 1 ,K - dis);
        }
    }
};