力扣hot100-->排序

发布于:2024-11-29 ⋅ 阅读:(24) ⋅ 点赞:(0)

目录

排序

1. 56. 合并区间

2. 215. 数组中的第K个最大元素

3. 347. 前 K 个高频元素

排序

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 小的元素。其工作原理与快速排序相似,但只会递归地处理包含目标元素的部分。
    • 在每次递归时,选择一个枢纽元素,并通过 分区 操作将数组分成两部分:左边部分小于枢纽元素,右边部分大于枢纽元素。
    • 分区操作:通过两个指针 iji 从左边开始,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 个数字。