本文共 1880 字，大约阅读时间需要 6 分钟。

题目：

  

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.

我的思路主要是分治方法，也就是快排的思路。不过在这里只需要检查一侧就可以，不需要像快排一样需要对中间元素的两侧进行排序。所以时间复杂度应该是log(n)，下面是具体代码：

class Solution {public:    int partition(vector
   
    &nums,int start,int end)    {            if(start == end)return start;            int flag = nums[start];                        int i=start-1;            int j;            for(j = start+1;j<=end;++j){                if(nums[j] >= flag){                    ++i;                    nums[i] = nums[j];                    nums[j] = nums[i+1];                }            }            nums[i+1] = flag;            return (i+1);    }        int findKthLargest(vector
    
     & nums, int k) {        int size = nums.size();        int low = 0;        int high = size-1;        if(k>size)return -1;        if(size == 1)return nums[0];       while(true){            int p = partition(nums,low,high);                        if((p-low)+1 ==  k)return nums[p];                        else if(k - 1 > (p-low) ){                k = k - (p-low) - 1;                low = p+1;            }                        else {                high = p-1;            }        }
    
   

};

看一下计算时间，好慢！！

然后我就想试一下用STL里面的sort函数偷一下懒，顺便比较一下两者的计算时间。用STL函数的代码如下，非常简单

class Solution {public:        int findKthLargest(vector
   
    & nums, int k) {        int size = nums.size();        int low = 0;        int high = size-1;        if(k>size)return -1;        if(size == 1)return nums[0];        sort(nums.begin(),nums.end());        return nums[size-k];    }};
   

看一下运行时间

              比自己写的要快好多。没想到别人排序后的算法比自己自然为的log(n)算法还要快，简直想不明白,，还有，难道大家都这么懒？！=。=。不过唯一可以知道的一件事情是：果然STL大法好。这个疑问留给以后读STL源码！ 打算把这个放在了解c++ template之后进行。加油！