力扣hot100--＞排序

排序

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 个数字。