Leetcode.215.Kth Largest Element

题目

给定一个数组, 输出第k大的数.

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

思路

进行从大到小排序, 第k-1即为第k大的数.

void findKthLargestSort(vector<int>& nums, int l, int r) {
      if (l < r) {
          int i = l, j = r, x = nums[l];
          while (i < j) {
              while (i < j && x > nums[j]) j--;
              if (i < j) nums[i++] = nums[j];
              while (i < j && nums[i] > x) i++;
              if (i < j) nums[j--] = nums[i];
          }
          nums[i] = x;
          findKthLargestSort(nums, l, i-1);
          findKthLargestSort(nums, i+1, r);
      }
  }

int findKthLargest(vector<int>& nums, int k) {
    findKthLargestSort(nums, 0, (int)nums.size()-1);
    return nums[k-1];
}

总结

掌握快速排序.