leetcode解题报告（31）：Kth Largest Element in an Array

描述

分析

代码如下:

class Solution {

public:

    int partition(vector<int>&nums,int p,int r)

    {

        int x = nums[r];

        int i = p - 1;

        for(int j = p; j != r; ++j)

            if(nums[j] < x)

                swap(nums[++i],nums[j]);

        swap(nums[i + 1],nums[r]);

        return i + 1;

    }

    int findKthLargest(vector<int>& nums, int k) {

        /*

        sort(nums.begin(),nums.end());

        return nums[nums.size() - k];

                                        */

        int p = 0,r = nums.size() - 1;

        while(true){

            int q = partition(nums,p,r);

            if(q < nums.size() - k)

                p = q + 1;

            else if(q > nums.size() - k)

                r = q - 1;

            else

                return nums[q];

        }

    }

};