【数据结构与算法】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之间的值都等于base
        quick_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] < base
        if (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 {                         // 左侧的子数组个数等于k
            for (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的最小值给B
            A.pop();         		// A弹出最小值
        } else {              		// 当前为偶数个值
            B.push(num);      		// B添加一个数值
            A.push(B.top());  		// B的最大值给A
            B.pop();          		// B弹出最大值
        }
    }
    double findMedian() {
        return A.size() != B.size() ? A.top() : (A.top() + B.top()) / 2.0;
    }
};