1. 題目
在未排序的數(shù)組中找到第 k 個最大的元素。請注意，你需要找的是數(shù)組排序后的第 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
說明:
你可以假設(shè) k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長度。
2. 思路
- 針對這個題目，我們首先想到的就是先用排序算法對數(shù)據(jù)從大到小進(jìn)行排序，然后直接返回降序后的第 K 個元素即可。
另外，我們也可以借鑒快速排序的思想。每次選取一個 pivot，將大于 pivot 的數(shù)放在 pivot 左邊，將小于 pivot 的數(shù)放在 pivot 右邊。
-
這時候，如果 pivot 正好是第 K 個數(shù)據(jù)，則 pivot 就是數(shù)組中的第 K 個最大元素。
1 -
如果 pivot 所在的位置小于 K ，則說明數(shù)組中的第 K 個最大元素位于 pivot 的右邊。此時，假設(shè) pivot 的位置為 which_max，which_max 是幾就代表 pivot 是數(shù)組中的第幾個最大元素。這時候，我們再從 pivot 右邊的數(shù)據(jù)中找到第 (K-which_max) 個最大元素即可。
2 -
如果 pivot 所在的位置大于 K ，則說明數(shù)組中的第 K 個最大元素位于 pivot 的左邊。這時候，pivot 左邊的數(shù)據(jù)全部大于 pivot，我們繼續(xù)從 pivot 左邊的數(shù)據(jù)中找第 K 個最大元素即可。
3 而其中的快速排序算法實(shí)現(xiàn)可以有兩種思想，具體可參考此處。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
return quick_sort(nums, 0, nums.size()-1, k);
}
// 第一種快排思想
int quick_sort(vector<int>& data, int left, int right, int k)
{
int i = left;
int j = right;
int pivot = data[right];
int len = right - left + 1;
if (left < right)
{
// 從大到小對數(shù)組進(jìn)行快排
while(i < j)
{
while(i < j && data[i] >= pivot) // 從左往右找第一個比 pivot 小的數(shù)
{
i++;
}
if (i < j)
{
data[j--] = data[i];
}
while(i < j && data[j] <= pivot) // 從右往左找第一個比 pivot 大的數(shù)
{
j--;
}
if (i < j)
{
data[i++] = data[j];
}
}
data[i] = pivot; // 此時 i == j
// pivot 此時位于索引 i 處，i - left + 1 表示 pivot 是第幾大的數(shù)
int which_max = i - left + 1;
if (which_max == k) // pivot 正好是第 k 大的數(shù)
{
return pivot;
}
// 第 k 大的數(shù)在 pivot 右邊，問題轉(zhuǎn)化為找右邊數(shù)組第 (k - which_max) 大的元素
// 比如 pivot 是第四大的數(shù)，要找第五大的數(shù)，則繼續(xù)找右邊數(shù)組第一大的數(shù)即可
else if(which_max < k)
{
return quick_sort(data, i + 1, right, k - which_max);
}
// 第 k 大的數(shù)在 pivot 左邊，問題轉(zhuǎn)化為找左邊數(shù)組第 k 大的元素
// 比如 pivot 是第三大的數(shù)，要找第二大的數(shù)，則繼續(xù)找左邊數(shù)組第二大的數(shù)即可
else
{
return quick_sort(data, left, i - 1, k);
}
}
else
{
return pivot;
}
}
// 第二種快排思想
int quick_sort(vector<int>& data, int left, int right, int k)
{
int i = left;
int j = left;
int pivot = data[right];
int len = right - left + 1;
if (left < right)
{
// 從大到小對數(shù)組進(jìn)行快排
for (; j < right; j++)
{
if (data[j] > pivot)
{
int temp = data[i];
data[i] = data[j];
data[j] = temp;
i++;
}
}
data[j] = data[i];
data[i] = pivot;
// pivot 此時位于索引 i 處，i - left + 1 表示 pivot 是第幾大的數(shù)
int which_max = i - left + 1;
if (which_max == k) // pivot 正好是第 k 大的數(shù)
{
return pivot;
}
// 第 k 大的數(shù)在 pivot 右邊，問題轉(zhuǎn)化為找右邊數(shù)組第 (k - which_max) 大的元素
// 比如 pivot 是第四大的數(shù)，要找第五大的數(shù)，則繼續(xù)找右邊數(shù)組第一大的數(shù)即可
else if(which_max < k)
{
return quick_sort(data, i + 1, right, k - which_max);
}
// 第 k 大的數(shù)在 pivot 左邊，問題轉(zhuǎn)化為找左邊數(shù)組第 k 大的元素
// 比如 pivot 是第三大的數(shù)，要找第二大的數(shù)，則繼續(xù)找左邊數(shù)組第二大的數(shù)即可
else
{
return quick_sort(data, left, i - 1, k);
}
}
else
{
return pivot;
}
}
};
