允许个人做动漫网站吗,wordpress固定链接优化,网站开发方法 优帮云,四川省建设工程造价信息网站文章目录 LeetCode#xff1a;堆和快排排序数组数组中的第K个最大元素 #xff08;Hot 100#xff09;前 K 个高频元素#xff08;Hot 100#xff09;数据流的中位数#xff08;Hot 100#xff09; LeetCode#xff1a;堆和快排
排序数组
排序数组
双向切分实现快排… 文章目录 LeetCode堆和快排排序数组数组中的第K个最大元素 Hot 100前 K 个高频元素Hot 100数据流的中位数Hot 100 LeetCode堆和快排
排序数组
排序数组
双向切分实现快排
class Solution {
private:void quick_sort(vectorint 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:vectorint sortArray(vectorint nums) {quick_sort(nums, 0, nums.size() - 1);return nums;}
};
三向切分实现快排 三向切分快速排序在处理包含大量重复元素的数组时比双向切分快速排序更快。
class Solution {
private:void quick_sort(vectorint 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:vectorint sortArray(vectorint nums) {quick_sort(nums, 0, nums.size() - 1);return nums;}
};数组中的第K个最大元素 Hot 100
数组中的第K个最大元素
堆 当我们想要找到数组中第k个最大的元素时我们应该维护一个大小为k的最小堆因为最小堆的堆顶元素总是最小的 class Solution {
public: int findKthLargest(std::vectorint nums, int k) { std::priority_queueint, std::vectorint, std::greaterint 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(vectorint 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] basenums[left..right] basenums[right1..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(vectorint 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 pairint, int lhs, const pairint, int rhs){return lhs.second rhs.second; // 按照频率从大到小排序}};vectorint topKFrequent(vectorint nums, int k) {unordered_mapint, int map;// 统计元素频率元素出现次数for(int i 0; i nums.size(); i)map[nums[i]];priority_queuepairint, int, vectorpairint, int, mycomparison pri_que;for(auto num_freq : map){pri_que.push(num_freq); if(pri_que.size() k) pri_que.pop(); // 只保留K个最高频元素}vectorint 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(vectorpairint, int v, int l, int r, vectorint 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);}}vectorint topKFrequent(vectorint nums, int k) {// 统计元素频率元素出现次数unordered_mapint, int map;for (auto num : nums) map[num ];// 将 unordered_map 转换为 vector 以便可以随机访问vectorpairint, int num_freq(map.begin(), map.end());vectorint result;// 使用快速选择算法查找前 k 大的频率qsort(num_freq, 0, num_freq.size() - 1, result, k);return result;}
};数据流的中位数Hot 100
数据流的中位数
class MedianFinder {
public:priority_queueint, vectorint, greaterint A; // 小顶堆保存较大的一半priority_queueint, vectorint, lessint 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;}
};
