排序
1. 56. 合并区间
中等
以数组 intervals
表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi]
。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]] 输出:[[1,6],[8,10],[15,18]] 解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入:intervals = [[1,4],[4,5]] 输出:[[1,5]] 解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示:
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> result;
int n = intervals.size();// 按照区间起始点排序
sort(intervals.begin(), intervals.end());for(int i = 0; i < n; ++i) {
// 如果结果为空或当前区间与最后一个区间不重叠,直接添加
if (result.empty() || result.back()[1] < intervals[i][0]) {
result.push_back(intervals[i]);
} else {
// 否则合并区间,更新结束点
result.back()[1] = max(result.back()[1], intervals[i][1]);
}
}return result;
}
};
2. 215. 数组中的第K个最大元素
中等
给定整数数组 nums
和整数 k
,请返回数组中第 k
个最大的元素。
请注意,你需要找的是数组排序后的第 k
个最大的元素,而不是第 k
个不同的元素。
你必须设计并实现时间复杂度为 O(n)
的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2 输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4
提示:
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104
class Solution {
public:
// quickselect 函数:使用快速选择算法查找第 k 个元素
int quickselect(vector<int> &nums, int l, int r, int k) {
if (l == r) // 递归终止条件,当左右边界相同,说明找到了目标元素
return nums[k]; // 返回找到的元素int partition = nums[l]; // 选择第一个元素作为枢纽元素
int i = l - 1, j = r + 1; // 初始化左右指针
// 分区操作,将元素分为两部分,左边部分小于枢纽,右边部分大于枢纽
while (i < j) {
do i++; while (nums[i] < partition); // 找到大于或等于枢纽的元素
do j--; while (nums[j] > partition); // 找到小于或等于枢纽的元素
if (i < j)
swap(nums[i], nums[j]); // 交换两个元素,使得左边小于枢纽,右边大于枢纽
}// 根据 k 的位置判断在哪个部分继续查找
if (k <= j) // 如果 k 在左边部分,继续在左边部分查找
return quickselect(nums, l, j, k);
else // 如果 k 在右边部分,继续在右边部分查找
return quickselect(nums, j + 1, r, k);
}// findKthLargest 函数:返回数组 nums 中第 k 大的元素
int findKthLargest(vector<int> &nums, int k) {
int n = nums.size(); // 数组的大小
return quickselect(nums, 0, n - 1, n - k); // 调用 quickselect 查找第 n-k 小的元素
}
};
解释:
-
quickselect
函数:- 这是快速选择算法的核心部分,目标是查找第
k
小的元素。其工作原理与快速排序相似,但只会递归地处理包含目标元素的部分。 - 在每次递归时,选择一个枢纽元素,并通过 分区 操作将数组分成两部分:左边部分小于枢纽元素,右边部分大于枢纽元素。
- 分区操作:通过两个指针
i
和j
,i
从左边开始,j
从右边开始,分别找到大于等于枢纽的元素和小于等于枢纽的元素,并进行交换。直到两个指针相遇,完成一次分区。 - 每次递归时,判断目标
k
是否在左部分或右部分,并根据位置选择继续递归哪个部分。
- 这是快速选择算法的核心部分,目标是查找第
-
findKthLargest
函数:- 为了查找第
k
大的元素,findKthLargest
调用quickselect
来查找第n-k
小的元素(因为在排序中,第k
大的元素是第n-k
小的元素,n
是数组的长度)。 quickselect(nums, 0, n - 1, n - k)
表示在整个数组范围内,查找第n-k
小的元素,最终得到第k
大的元素。
- 为了查找第
奇思妙想:
随便写的就对了,sort函数平均时间复杂度为 O(n log n),
力扣没判错,额,嘶~~
大家看着玩玩,这绝对不是正确解答。哈哈哈
网友解释说是判题的时候数据量没拉满,拉满的话就超时了,千万不要这样写哟,否则面试出门左拐。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end()); // 排序
int n = nums.size() - k; // 找到第 k 大的元素的位置
return nums[n]; // 返回该元素
}
};
3. 347. 前 K 个高频元素
中等
给你一个整数数组 nums
和一个整数 k
,请你返回其中出现频率前 k
高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2:
输入: nums = [1], k = 1 输出: [1]
提示:
1 <= nums.length <= 105
k
的取值范围是[1, 数组中不相同的元素的个数]
- 题目数据保证答案唯一,换句话说,数组中前
k
个高频元素的集合是唯一的
// 定义自定义比较器,用于构造小顶堆
class mycomparison {
public:
// 重载 () 运算符
// 比较两个 pair 的第二个元素(即频率),实现从小到大的排列
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second; // 小顶堆:频率小的优先
}
};class Solution {
public:
// 主函数:获取数组中频率最高的前 K 个元素
vector<int> topKFrequent(vector<int>& nums, int k) {
// 使用哈希表统计每个元素的出现次数
unordered_map<int, int> unMap;
for (int& num : nums) {
unMap[num]++; // 记录每个数字的频率
}// 定义优先队列(小顶堆),使用自定义比较器
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;// 遍历哈希表,将键值对插入到小顶堆中
for (auto& [key, value] : unMap) {
pq.push({key, value}); // 插入键值对// 如果堆的大小超过 k,则移除堆顶元素
if (pq.size() > k) {
pq.pop(); // 弹出频率最低的元素
}
}// 将堆中的元素提取出来,存入结果数组
vector<int> result;
while (!pq.empty()) {
result.emplace_back(pq.top().first); // 提取元素的键
pq.pop(); // 移除堆顶
}return result; // 返回前 K 个高频元素
}
};
解释:
定义了一个优先队列(即小顶堆)。
- 堆内存储:
pair<int, int>
类型的键值对,first
是数字,second
是频率。 - 比较规则:使用自定义比较器
mycomparison
,保证堆顶是当前频率最小的元素。
- 使用哈希表统计每个数字的频率。
- 使用小顶堆(优先队列)来维护频率最高的 kkk 个数字。
- 堆的大小始终保持为 kkk。
- 当堆的大小超过 kkk 时,移除堆顶元素(频率最小)。
- 最终,堆中剩下的就是频率最高的 kkk 个数字。