215. 数组中的第 K 个最大元素
215. 数组中的第K个最大元素 - 力扣（LeetCode）
class Solution {
template<typename Compare = std::less<>>
void PercolateDown(vector<int> &V, int N, Compare C = {}) {
int Size = V.size();
// XXX size() returns size_t type, which is an UNSIGNED value!!!
// while (N <= V.size() / 2 - 1) {
while (N <= Size / 2 - 1) {
int L = N * 2 + 1, R = N * 2 + 2;
int Chosen = N;
if (C(V[Chosen], V[L]))
Chosen = L;
// Mind that right child possibly doesn't exist. Left always exist though.
// Also, we must compare with LargestIdx instead of N here, since we
// want the max of THREE. The comparison pattern is NL -> LR.
if (R < Size && C(V[Chosen], V[R]))
Chosen = R;
if (Chosen == N)
return;
std::swap(V[N], V[Chosen]);
N = Chosen;
}
}
void BuildHeap(vector<int> &V) {
for (int i = V.size() / 2 - 1; i >= 0; --i)
PercolateDown(V, i);
}
void Pop(vector<int> &V) {
std::swap(V.front(), V.back());
V.resize(V.size() - 1);
PercolateDown(V, 0);
}
public:
int findKthLargest(vector<int>& nums, int k) {
BuildHeap(nums);
for (int i = 1; i < k; ++i)
Pop(nums);
return nums.front();
}
};
我服了啊，我真的受不了了，size() 返回的是 size_t，如果你不强制转换的话在前面把它跟 int 比较的时候 int 会被自动提升到 size_t——参见 Implicit conversions - cppreference.com——然后整个式子就变成无符号数比较了。我服了啊，我操。
话说回来，关于堆的几个操作要搞搞清楚。从 Size / 2 - 1 下标开始构建堆的原因是，这个下标是「倒数第一个非叶子节点」；PercolateDown() 在选择最大（最小）下标的时候是三路比较（LN 和 NR），所以要设一个 Chosen 作为中间变量；Pop() 的时候要把最后一个元素交换到堆顶，然后向下冒泡。
此外你可以发现，这里的解法是原地建堆的。我一开始其实也写了一个 class Heap 但后来发现没这个必要，还徒增空间复杂度。
但是除了官解给的大根堆的写法，事实上还有一种小根堆的写法，也比较直观：先原地建立一个尺寸为 \(k\) 的小根堆，然后一边读取数组的后续内容，一边调整堆，完成后处在堆顶的即为第 \(k\) 大的元素。
class Solution {
template<typename Compare = std::less<>>
void PercolateDown(vector<int> &V, int N, int Size, Compare C = {}) {
while (N <= Size / 2 - 1) {
int L = N * 2 + 1, R = N * 2 + 2;
int Chosen = N;
if (C(V[Chosen], V[L]))
Chosen = L;
if (R < Size && C(V[Chosen], V[R]))
Chosen = R;
if (Chosen == N)
return;
std::swap(V[N], V[Chosen]);
N = Chosen;
}
}
template<typename Compare = std::less<>>
void BuildHeap(vector<int> &V, int Size, Compare C = {}) {
for (int i = Size / 2 - 1; i >= 0; --i)
PercolateDown(V, i, Size, C);
}
template<typename Compare = std::less<>>
void Pop(vector<int> &V, int Size, Compare C = {}) {
std::swap(V.front(), V.back());
PercolateDown(V, 0, Size - 1, C);
}
public:
int findKthLargest(vector<int>& nums, int k) {
// Firstly, make a heap of k elements in-place.
BuildHeap(nums, k, std::greater<int>());
for (int i = k; i < nums.size(); ++i) {
// Then, read the remaining elements and check if it's needed to adjust
// the heap. For this problem, we choose elements larger than top.
if (nums[i] > nums.front()) {
std::swap(nums.front(), nums[i]);
PercolateDown(nums, 0, k, std::greater<int>());
}
}
return nums.front();
}
};
其实这个就叫 Top-K，我是真没想到这个名字竟然是这个意思。不过这相比原地建堆的操作，时间复杂度 \(\mathrm O(n\log k)\) 没有特别多的提升，且本题不要求实现 online 算法，所以官解似乎也没有继续考虑。
至于快排，采用 y 总的模板可以这么写，但是有两件事情要注意一下。
class Solution {
// For quicksort related algorithms, we'll use inclusive range. You can see
// that both musl libc and glibc use inclusive ranges.
int QuickFind(vector<int> &A, int L, int R, int K) {
if (L == R)
return A[K];
int Pivot = A[L], i = L - 1, j = R + 1;
while (i < j) {
while (A[++i] < Pivot);
while (A[--j] > Pivot);
if (i < j)
std::swap(A[i], A[j]);
}
// If you use this kind of quicksort algorithm, you'll find that [L, j] are
// all LESS THAN (<) Pivot, and [j + 1, R] are NOT LESS THAN (>=) Pivot.
// However, where the pivot lays can't be determined. This is really
// interesting. Keep that in mind and just use it for now.
if (j < K)
return QuickFind(A, j + 1, R, K);
else
return QuickFind(A, L, j, K);
}
public:
int findKthLargest(vector<int>& nums, int k) {
int N = nums.size();
// Remember that we need to find the kth LARGEST number, not smallest; so
// we need to pass N - k here instead of k.
return QuickFind(nums, 0, N - 1, N - k);
}
};
第一件事情是，这种模板在每次划分之后并不保证 pivot 的位置，而只是以下标 \(j\) 为界，把数组分成了 \([L, j]<\text{Pivot}\) 和 \((j, R]>=\text{Pivot}\) 两个部分；其次，要注意这样排序之后数组是正序的，所以我们应该传入的参数应该是 \(N-k\) 而不是 \(k\)。
关于 pivot 位置啊、分区啊之类的事情就之后再研究吧，现在还是多接触题型要紧。
二刷
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int K = nums.size() - k;
int l = 0, r = nums.size() - 1;
// Keep in mind that every time the loop completed, the original nums[] was
// modified. So we'll EVENTUALLY move Kth largest number to our l pointer.
// The swap() below indicates this clearly.
while (l != r) {
int Pivot = nums[l];
int i = l - 1, j = r + 1;
while (i < j) {
// You muse remember those operator directions!
while (nums[++i] < Pivot) {}
while (nums[--j] > Pivot) {}
if (i < j)
swap(nums[i], nums[j]);
}
if (j < K)
l = j + 1;
else
r = j;
}
// Returning nums[l] is basically the same as returning nums[K]. That's
// because if we went here, we already have l == r == K as stated above.
return nums[l];
}
};
千万要注意，快速选择算法本质上就是快排。因为我们是通过交换的手段，修改原数组，从而达到逐步将待查元素放到 \(K\) 的位置上的。理解了这一点之后，就可以理解为什么官解的不动点写的是 if (l == r) return nums[k]; 了。
还有就是他妈的把大于小于号搞搞清楚。一开始写反了我是真绷不住了。
class Solution {
static void PercolateDown(vector<int> &V, int i, int Size) {
// The minus one here is to convert 1-indexed Size to 0-indexed index.
while (i <= Size / 2 - 1) {
// We use 0-indexed index here.
int Left = i * 2 + 1, Right = i * 2 + 2;
int Smallest = i;
if (V[Left] < V[Smallest])
Smallest = Left;
if (Right < Size && V[Right] < V[Smallest])
Smallest = Right;
swap(V[i], V[Smallest]);
// Notice that we don't have to recurse. Just use the while loop is fine.
if (Smallest == i)
return;
if (Smallest == Left)
i = Left;
else
i = Right;
}
}
static void BuildHeap(vector<int> &V, int Size) {
// Still, mind the minus one here.
for (int i = Size / 2 - 1; i >= 0; --i)
PercolateDown(V, i, Size);
}
public:
int findKthLargest(vector<int>& nums, int k) {
BuildHeap(nums, k);
for (int i = k; i < nums.size(); ++i) {
if (nums[i] > nums.front()) {
swap(nums[i], nums.front());
PercolateDown(nums, 0, k);
}
}
return nums.front();
}
};
Top-K 的堆还是得多写写，主要是注意 Size 是一个 1-indexed 的东西，所以要作一个 \(-1\) 变换，然后就是 PercolateDown() 里头其实用不着写递归，直接一个 while 就解决了，毕竟就算要写也是尾递归，跟上面那个迭代版快选算法一样的。
三刷
class Solution {
void MakeHeap(vector<int> &H) {
for (int i = H.size() / 2 - 1; i >= 0; --i)
PercolateDown(H, i);
}
void PercolateDown(vector<int> &H, int i) {
// This will ensure i is non-leaf.
while (i <= H.size() / 2 - 1) {
int SmallestIdx = i;
// This won't work?? Why??
if (H[SmallestIdx] > H[i * 2 + 1])
SmallestIdx = i * 2 + 1;
if (i * 2 + 2 < H.size() && H[SmallestIdx] > H[i * 2 + 2])
SmallestIdx = i * 2 + 2;
if (i == SmallestIdx)
break;
swap(H[i], H[SmallestIdx]);
i = SmallestIdx;
}
}
public:
int findKthLargest(vector<int>& nums, int k) {
vector<int> H(nums.begin(), nums.begin() + k);
MakeHeap(H);
// bro wtf
// for (int i = k; i < nums.size(); ++k) {
for (int i = k; i < nums.size(); ++i) {
if (nums[i] > H.front()) {
swap(nums[i], H.front());
PercolateDown(H, 0);
}
}
return H.front();
}
};
一种非原地的写法，虽然还是推荐原地建堆，但这个写法大体上也是正确的——然而在\(k=1\)时竟然会出现越界问题？我操，为什么啊？按理说它完全进不去循环体啊？
不管了，以后还是用原地解法吧，原地解法真没什么问题。此外就是注意比较的时候要用逐步比较的思想，也就是三个里面找最小永远是跟SmallestIdx比，而不是用某些固定的index去比。