題目鏈接

215. 數組中的第K個最大元素 - 力扣（LeetCode）

題目解析

算法原理

解法一:

直接理由java內部的排序函數,Arrays.sort()進行排序, 然后我們直接返回第k個最大的元素

nums[nums.length-k]

解法二:

使用堆

我們先把所有元素丟到大根堆里面,然后取k次堆頂元素

PriorityQueue<Integer> heap = new PriorityQueue<>((a,b)->b-a);

解法三:?

三指針法, 數組分三塊

代碼編寫

解法一:

class Solution {public int findKthLargest(int[] nums, int k) {// 排序Arrays.sort(nums);return nums[nums.length - k];}
}

解法二:

class Solution {public int findKthLargest(int[] nums, int k) {// 利用大根堆PriorityQueue<Integer> heap = new PriorityQueue<>((a,b)-> b-a);// 把元素放進大根堆for(int x : nums){heap.offer(x);}// 取第k個while(--k != 0){heap.poll();}return heap.poll();}
}

解法三

class Solution {// 交換private static void swap(int[] nums, int index1, int index2) {int tmp = nums[index1];nums[index1] = nums[index2];nums[index2] = tmp;}// 遞歸，分三段private static int quickSort(int[] nums, int l, int r, int k) {// l, r 是用來固定左右端點的int left = l - 1;int right = r + 1;// 獲取區間中間的元素作為 keyint key = nums[(l + r) / 2];  // 修改這里，取中間的值// 數組分成四段// [l,left]<key,[left+1,i]==key,[i+1,right-1]未知,[right,r]>key;int i = l;  // 從區間的開始進行遍歷while (i < right) {// 如果是 < keyif (nums[i] < key) {swap(nums, ++left, i++);} else if (nums[i] == key) {// 如果是 == keyi++;} else {// 如果是 > keyswap(nums, --right, i);}}// 此時分成三塊: [l, left]<key [left + 1, right - 1]==key [right, r]>key// 分類討論 [l, left] [left + 1, right - 1] [right, r]int b = (right - 1) - (left + 1) + 1;  // 中間部分的長度int c = r - right + 1;  // [right, r] 部分的長度if (c >= k) {// 去 [right, r] 查找第 k 大return quickSort(nums, right, r, k);} else if ((b + c) >= k) {// 如果中間部分就是第 k 大，直接返回return key;} else {// 去 [l, left] 查找第 k - b - c 大return quickSort(nums, l, left, k - b - c);}}public int findKthLargest(int[] nums, int k) {return quickSort(nums, 0, nums.length - 1, k);}
}

為什么是k-b-c大? 下面是ai的解釋
在快速排序（Quick Sort）中，我們通過分區操作將數組分為三部分：

1.小于基準值（key）的部分
2.等于基準值的部分
3.大于基準值的部分

我們希望找到第 k 大的元素。在快速排序的過程中，我們每次選擇一個基準值（key）并進行分區，接下來，我們遞歸地在其中一部分繼續查找目標元素。
問題核心
假設我們有一個 k 值，表示我們要找到第 k 大的元素。在分區后，數組被分為三部分：

[l, left] 這部分元素都小于基準值 key
[left + 1, right - 1] 這部分元素等于基準值 key
[right, r] 這部分元素都大于基準值 key

我們已經知道，在這些分區中，key 的位置非常關鍵。接下來，我們就要根據 k 和這些部分的大小來決定遞歸的方向。
代碼邏輯解釋
考慮下面幾個變量：

b：等于 key 的元素的個數。
c：大于 key 的元素的個數。

那么，b + c 是右邊部分（即大于 key 的部分加上等于 key 的部分）的元素總數。
如果 k 大于 b + c，意味著我們要找的第 k 大的元素不在右邊（即大于 key 的部分和等于 key 的部分），而是在左邊（小于 key 的部分）。因此，我們遞歸地去左邊查找。
但是，左邊的部分有一些特殊情況需要考慮：

左邊的部分包含了所有小于 key 的元素，因此找第 k 大的元素時，要跳過這些小于 key 的元素。
1由于已經知道有 b 個元素等于 key，而且右邊有 c 個大于 key 的元素，所以我們實際需要在左邊找的是第 k - b - c 大的元素。

為什么是 k - b - c

我們已經知道：
c 是大于 key 的元素數量。

b 是等于 key 的元素數量。
因此，如果我們要找的是第 k 大的元素，在遞歸調用時，要在左邊查找的是：
去掉 c 個大于 key 的元素，
去掉 b 個等于 key 的元素，
所以我們要查找的是 第 k - b - c 大的元素。

總結

k 是我們要找的第 k 大的元素。
b 是等于 key 的元素個數。
c 是大于 key 的元素個數。

因此，在左邊查找時，我們要尋找的元素是第 k - b - c 大的元素，原因是我們已經排除了右邊部分的元素（大于 key 和等于 key 的部分）。

二刷

class Solution {//交換void swap(int[] nums, int index1, int index2) {int tmp = nums[index1];nums[index1] = nums[index2];nums[index2] = tmp;}int quickSort(int[] nums, int l, int r, int k) {// 定義移動邊界int left = l - 1;int right = r + 1;int key = nums[(right + left) / 2];// 遍歷int i = l;while (i < right) {// 數組分四塊if (nums[i] < key) {// 去左邊swap(nums, i++, ++left);} else if (nums[i] == key) {// 直接往后走i++;} else {// 去右邊swap(nums, i, --right);}}// 此時分為三塊:[l,left]<key [left+1,right-1]=key [right,r]>key// 去找第k個最大的元素int b = (right - 1) - (left + 1) + 1; //中間部分int c = r - right + 1; // 右邊部分if (c >= k) {// 說明第k個最大在右邊部分return quickSort(nums, right, r, k);} else if ((b + c) >= k) {// 說明第k個最大在中間部分return key;} else {// 說明第k個最大在左邊部分，調整kreturn quickSort(nums, l, left, k - b - c);}}public int findKthLargest(int[] nums, int k) {// 使用快排來找到數組中第k個最大元素return quickSort(nums, 0, nums.length - 1, k);}
}

?