快排应用：数组中第K大元素

背景

学习了快排之后，主要了解了分治思想。所以在LeetCode上看到了一个经典的题目，所以尝试使用快排解决。

题目

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4>
输出: 4

说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

图解

首先，我们选择一个参考索引，在分治实现之后，所有小于参考值的元素都在其左侧，大于的在右侧。从而将数组分成了两个部分，然后比较索引值的位置和目标索引N - k的值大小，从而确认在哪边继续递归处理。
简单总结来说：

• 随机选择一个参考索引pIndex

• 使用划分算法将数组pIndex放在合适的位置，将数组分成两个部分。

• 比较pIndex和N - k决定在哪边继续递归处理。

  
  k_01.png

代码

 class Solution {
 public:
   int findKthLargest(vector<int>& nums, int k) {
     int leftIndex = 0;
     int rightIndex = nums.size() - 1;
     int targetIndex = nums.size() - k;
     return findKthLargest(nums, leftIndex, rightIndex, targetIndex);
   }
​
   int findKthLargest(vector<int>& nums, int leftIndex, int rightIndex, int targetIndex) {
     int i = leftIndex;
     int j = rightIndex;
     int pIndex = leftIndex;
​
     int privot = nums[pIndex];
     while (i != j) {
       while (i < j && nums[j] >= privot) {
         j--;
       }
​
       while (i < j && nums[i] <= privot) {
         i++;
       }
​
       if (i < j) {
         int tmepValue = nums[i];
         nums[i] = nums[j];
         nums[j] = tmepValue;
       }
     }

     // pIndex的值和i互换
     nums[leftIndex] = nums[i];
     nums[i] = privot;

     pIndex = i;
     if (pIndex == targetIndex) {
       return nums[pIndex]; // 找到直接返回
     } else if (pIndex > targetIndex) {
       return findKthLargest(nums, leftIndex, pIndex - 1, targetIndex);
      } else {
       return findKthLargest(nums, pIndex + 1, rightIndex, targetIndex);
     }
   }
};

复杂度分析

快排我们知道其复杂度是O(NlogN)，这里我们只需要对包含N - k小的元素的那部分。所以平均时间复杂度下降到O(N)。
时间复杂度：O(NlogN)
空间复杂度：O(1)