【数据结构与算法】LeetCode：堆和快排

LeetCode：堆和快排

排序数组

排序数组

双向切分实现快排：

class Solution {
private:void quick_sort(vector<int>& nums, int left, int right){if (left >= right) return;// 随机选择基准值int k = rand() % (right - left + 1) + left; swap(nums[right], nums[k]);int base = nums[right];int slow = left; // slow之前都是小于等于base的for(int fast = left; fast < right; fast++){ // 从left开始if(nums[fast] <= base){ swap(nums[slow], nums[fast]); slow++;}}swap(nums[slow], nums[right]); quick_sort(nums, left, slow - 1);  // 比base小的部分 quick_sort(nums, slow + 1, right); // 比base大的部分}public:vector<int> sortArray(vector<int>& nums) {quick_sort(nums, 0, nums.size() - 1);return nums;}
};

三向切分实现快排：
三向切分快速排序在处理包含大量重复元素的数组时比双向切分快速排序更快。

class Solution {
private:void quick_sort(vector<int>& nums, int begin, int end){if (begin >= end) return;// 随机选择基准值int k = rand() % (end - begin + 1) + begin; swap(nums[end], nums[k]);int base = nums[end];// 三向切分：使用 left 和 right 指针来划分小于、等于和大于基准值的区域。int left = begin, i = begin, right = end;while (i <= right) {if (nums[i] < base) {  // 小于base的换到左边swap(nums[left], nums[i]);left++;i++;} else if (nums[i] > base) { // 大于base的换到右边swap(nums[i], nums[right]);right--;} else { // 等于base的元素直接跳过，所以交换操作的次数也减少了i++;}}// left 和right之间的值都等于basequick_sort(nums, begin, left - 1);quick_sort(nums, right + 1, end);}public:vector<int> sortArray(vector<int>& nums) {quick_sort(nums, 0, nums.size() - 1);return nums;}
};

数组中的第K个最大元素 （Hot 100）

数组中的第K个最大元素

堆：
当我们想要找到数组中第k个最大的元素时，我们应该维护一个大小为k的最小堆，因为最小堆的堆顶元素总是最小的：

  
class Solution {  
public:  int findKthLargest(std::vector<int>& nums, int k) {  std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap; // 最小堆  // 遍历数组，维护一个大小为K的最小堆  for (int num : nums) {  if (min_heap.size() < k) {  min_heap.push(num);   } else if (num > min_heap.top()) {  min_heap.pop();      // 弹出最小值min_heap.push(num);  // 加入新值  }  }  // 堆顶为第K大的元素return min_heap.top();  }  
};

快排：

class Solution {
public:int quickselect(vector<int> &nums, int begin, int end, int k) {// 随机选择基准值int picked = rand() % (end - begin + 1) + begin;swap(nums[picked], nums[end]);int base = nums[end];int left = begin,right = end,i = begin;  while (i <= right) {if (nums[i] > base) {swap(nums[left], nums[i]);left++;i++;} else if (nums[i] < base) {swap(nums[i], nums[right]);right--;} else {i++;}}//nums[begin..left-1] > base，nums[left..right] == base，nums[right+1..end] < baseif (k >= left && k <= right) return nums[k];                      // k 落在等于 base 的区间else if (k < left) return quickselect(nums, begin, left - 1, k);  // k 在左边else return quickselect(nums, right + 1, end, k);                  // k 在右边} int findKthLargest(vector<int> &nums, int k) {int n = nums.size();return quickselect(nums, 0, n - 1, k - 1);}
};

前 K 个高频元素（Hot 100）

前 K 个高频元素

堆：

class Solution {
public:class mycomparison{public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs){return lhs.second > rhs.second; // 按照频率从大到小排序}};vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> map;// 统计元素频率<元素，出现次数>for(int i = 0; i < nums.size(); i++)map[nums[i]]++;priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;for(auto num_freq : map){pri_que.push(num_freq); if(pri_que.size() > k) pri_que.pop();  // 只保留K个最高频元素}vector<int> result(k);for(int i = 0; i < k; i++){result[i] = pri_que.top().first;pri_que.pop();}return result;}};

快排：

class Solution {
public:void qsort(vector<pair<int, int>>& v, int l, int r, vector<int>& result, int k) {// 随机选择基准值int picked = rand() % (r - l + 1) + l;swap(v[picked], v[r]);int base = v[r].second;int i = l; for (int j = l; j < r; j++) {if (v[j].second >= base) {  // 找到频率大于等于基准值的元素swap(v[i], v[j]);      // 将大于等于基准值的元素放到左边i++;}}swap(v[i], v[r]);if (k < i - l + 1) {            // 左侧的子数组个数大于k，包含前 k个高频元素qsort(v, l, i - 1, result, k); } else if (k > i - l + 1) {     // 左侧的子数组个数小于k// k个高频元素包括左侧子数组的全部元素以及右侧子数组中的部分元素for (int m = l; m <= i; m++) result.push_back(v[m].first); // 左侧子数组的全部元素qsort(v, i + 1, r, result, k - (i - l + 1));               // 右侧子数组中的部分元素}else {                         // 左侧的子数组个数等于kfor (int m = l; m <= i; m++) result.push_back(v[m].first);}}vector<int> topKFrequent(vector<int>& nums, int k) {// 统计元素频率<元素，出现次数>unordered_map<int, int> map;for (auto& num : nums) map[num ]++;// 将 unordered_map 转换为 vector 以便可以随机访问vector<pair<int, int>> num_freq(map.begin(), map.end());vector<int> result;// 使用快速选择算法查找前 k 大的频率qsort(num_freq, 0, num_freq.size() - 1, result, k);return result;}
};

数据流的中位数（Hot 100）

数据流的中位数

class MedianFinder {
public:priority_queue<int, vector<int>, greater<int>> A; // 小顶堆，保存较大的一半priority_queue<int, vector<int>, less<int>> B;    // 大顶堆，保存较小的一半MedianFinder() { }void addNum(int num) {  if (A.size() != B.size()) { // 当前为奇数个值A.push(num);            // A添加一个数值B.push(A.top()); 		// A的最小值给BA.pop();         		// A弹出最小值} else {              		// 当前为偶数个值B.push(num);      		// B添加一个数值A.push(B.top());  		// B的最大值给AB.pop();          		// B弹出最大值}}double findMedian() {return A.size() != B.size() ? A.top() : (A.top() + B.top()) / 2.0;}
};