LintCode第k大元素

题目描述

  在数组中找到第 k 大的元素。

样例输入

  n = 1, nums = [1,3,4,2]   n = 3, nums = [9,3,2,4,8]

样例输出

  4   4

---

  此题最好采用$O(n)$的时间复杂度的方法进行求解，即快排中的划分方法。经过一次划分，可以确定一个数在数组中的最终位置，如果它的坐标等于k - 1，那么它就是第k大的元素，否则根据情况选择左边或右边的区间。因为在$O(n)$的时间内将一个规模为$n$的问题简化为一个规模近似$n/2$的问题，所以可以得到一个关于时间的递推关系：$T(n)=T(n/2)+O(n)$,由此可知该算法的时间复杂度为$O(n)$。

代码如下：

class Solution { public: int partition(vector<int>& nums, int k, int start, int end) { if(start == end) return nums[start]; int mid = start + (end - start) / 2; int midval = nums[mid]; int p = start, q = end; while(p <= q) { while(p <= q && nums[p] > midval) ++p; while(p <= q && nums[q] < midval) --q; if(p <= q) { swap(nums[p], nums[q]); ++p; --q; } } /*经过一次划分，数组区间[start, end]被分为[start, q], r, [p, end] *三个部分,其中r = q + 1 = p - 1。nums[r]对应每次划分时确定位置的数。 */ if(k - 1 == q + 1) return nums[q + 1]; if(k - 1 > q + 1) return partition(nums, k, p, end); if(k - 1 < q + 1) return partition(nums, k, start, q); } int kthLargestElement(int n, vector<int> &nums) { int len = nums.size() - 1; if(n > nums.size()) return -1; return partition(nums, n, 0, len); } };