Kth Largest Element in an Array

题目来源
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.

一开始没有理解题目，以为重复的两个也算一个，后来发现不是。
想想直接排序，从后往前数k个不就可以啦？

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

想想应该有O(n)的方法。