写在前面
快速排序(快速选择)
应用 partition 的快速选择算法
原理
k 的值小于等于左区间的长度-1(即 m-l), 说明不能确定满足条件的值, 继续划分(选择), 否则可以先选出 l 到 m 区间的值, 这段区间的值一定满足条件, 在这种情况下, 如果此时 k 要比 m 到 l 区间的长度+2(即m-l+1) 还大(因为前面记录结果时候记录的数目为 m-l+1), 那就可以划分这个区间了…
题目
215. 数组中的第K个最大元素;(仅取第 k 个)
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
srand(time(0));
int n = nums.size(), idx = n - k;
auto partition = [&](int l, int r) {
swap(nums[rand() % (r - l + 1) + l], nums[r]); // random
int pivot{nums[r]}, i{l};
for (int j{l}; j < r; ++j)
if (nums[j] < pivot) swap(nums[i++], nums[j]);
swap(nums[i], nums[r]);
return i; // pivot 新位置
};
function<int(int, int)> quickSelect = [&](int l, int r) {
int m = partition(l, r);
if (m == idx)
return nums[idx];
else
return m < idx ? quickSelect(m + 1, r) : quickSelect(l, m - 1);
};
return quickSelect(0, n - 1);
}
};
开了随机化之后速度快很多. 算法导论也对此有介绍:
9.2 期望为线性时间的选择算法
347. 前 K 个高频元素;剑指 Offer 40. 最小的k个数; (用小根堆更普适. 前 k 个)
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
srand(time(0));
unordered_map<int, int> cnt;
for (auto num : nums) ++cnt[num];
vector<pair<int, int>> pairs(cnt.begin(), cnt.end());
vector<int> ans;
auto partition = [&](int l, int r) {
swap(pairs[rand() % (r - l + 1) + l], pairs[r]); // random
int pivot{pairs[r].second}, i{l};
for (int j{l}; j < r; ++j) // 按出现次数降序排序
if (pairs[j].second >= pivot)
swap(pairs[i++], pairs[j]);
swap(pairs[i], pairs[r]);
return i; // pivot 新位置
};
function<void(int, int, int)> quickSelect = [&](int l, int r, int k) {
int m = partition(l, r);
if (k <= m - l)
quickSelect(l, m - 1, k);
else {
for (int i{l}; i <= m; ++i)
ans.emplace_back(pairs[i].first);
if (k > m - l + 1)
quickSelect(m + 1, r, k - (m - l + 1));
}
};
quickSelect(0, pairs.size() - 1, k);
return ans;
}
};
面试题 17.14. 最小K个数 - 力扣（Leetcode）;
class Solution {
public:
vector<int> smallestK(vector<int>& arr, int k) {
vector<int> ans;
if (k == 0)
return ans;
ans.reserve(k);
auto p = [&](int l, int r) {
swap(arr[rand() % (r - l + 1) + l], arr[r]);
int j{l}, pivot{arr[r]};
for (int i{l}; i < r; ++i) {
if (arr[i] <= pivot) // 递增序
swap(arr[i], arr[j++]);
}
swap(arr[j], arr[r]);
return j;
};
function<void(int, int, int)> f = [&](int l, int r, int k) {
int m = p(l, r);
if (k <= m - l)
f(l, m - 1, k);
else {
for (int i{l}; i <= m; ++i)
ans.emplace_back(arr[i]);
if (k > m - l + 1)
f(m + 1, r, k - (m - l + 1));
}
};
f(0, arr.size() - 1, k);
return ans;
}
};
需要注意的点
- 随机化时候取模加上 1, 因为区间为 0 时候(l==r)会导致模 0 Error.