在数组中找到第 k 大的元素。(你可以交换数组中的元素的位置)

点此在线做题

样例 1：

输入： n = 1, nums = [1,3,4,2] 输出： 4  

样例 2：

输入： n = 3, nums = [9,3,2,4,8] 输出： 4  

[题解]

算法：快速选择算法

最容易想到的就是直接排序，返回第 k 大的值。时间复杂度是 O(nlogn)，这里提供 O(n)的解法。

这题其实是快速排序算法的变体，在九章算法班中也有详细讲解。通过快速排序算法的 partition 步骤，可以将小于 pivot 的值划分到 pivot 左边，大于 pivot 的值划分到 pivot 右边，所以可以直接得到 pivot 的 rank 。从而缩小范围继续找第 k 大的值。

partition 步骤：

• 令 left = start，right = end，pivot = nums[left]。
• 当 nums[left] < pivot 时，left 指针向右移动。
• 当 nums[right] > pivot 时，right 指针向左移动。
• 交换两个位置的值，right 指针左移，left 指针右移。
• 直到两指针相遇，否则回到第 2 步。 每次 partition 后根据 pivot 的位置，寻找下一个搜索的范围。

复杂度分析

设数组长度为 n

时间复杂度 O(n)

• 对一个数组进行 partition 的时间复杂度为 O(n)。
• 分治，选择一边继续进行 partition 。
• 所以总的复杂度为 T(n) = T(n / 2) + O(n)，总时间复杂度依然为 O(n)。

空间复杂度 O(1)

只需要快速选择游标的 O(1)额外空间。

public class Solution {     /**      * @param n: An integer      * @param nums: An array      * @return: the Kth largest element      */     public int kthLargestElement(int k, int[] nums) {         int n = nums.length;         // 为了方便编写代码，这里将第 k 大转换成第 k 小问题。         k = n - k;         return partition(nums, 0, n - 1, k);     }     public int partition(int[] nums, int start, int end, int k) {         int left = start, right = end;         int pivot = nums[left];          while (left <= right) {             while (left <= right && nums[left] < pivot) {                 left++;             }             while (left <= right && nums[right] > pivot) {                 right--;             }             if (left <= right) {                 swap(nums, left, right);                 left++;                 right--;             }         }          // 如果第 k 小在右侧，搜索右边的范围，否则搜索左侧。         if (k <= right) {             return partition(nums, start, right, k);         }         if (k >= left) {             return partition(nums, left, end, k);         }         return nums[k];     }     public void swap(int[] nums, int x, int y) {         int temp = nums[x];         nums[x] = nums[y];         nums[y] = temp;     } }  

更多题解参见

大佬有話說 (0)