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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/923258.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

一分钟学习数据安全——数据安全风险的系统化应对思路

数据是组织的重要资产&#xff0c;未经授权的数据访问可能导致数据泄露、数据篡改、隐私侵犯和合规风险等问题。企业可以通过数据访问控制来提高信息系统在数据全生命周期管理中的安全性。企业可以引入IAM系统&#xff0c;来控制身份来管理权限。通过对用户访问权限的管理和合适…

免费实用在线AI工具集合 - 加菲工具

免费在线工具-加菲工具 https://orcc.online/ 在线录屏 https://orcc.online/recorder 时间戳转换 https://orcc.online/timestamp Base64 编码解码 https://orcc.online/base64 URL 编码解码 https://orcc.online/url Hash(MD5/SHA1/SHA256…) 计算 https://orcc.online/h…

五种创建k8s的configMap的方式及configmap使用

configmap介绍 Kubernetes 提供了 ConfigMap 来管理应用配置数据&#xff0c;将配置信息从容器镜像中解耦&#xff0c;使应用更灵活、可移植。 1、基于一个目录来创建ConfigMap ​ 你可以使用 kubectl create configmap 基于同一目录中的多个文件创建 ConfigMap。 当你基于目…

ssm185大学学术交流论坛+vue(论文+源码)_kaic

摘 要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&#xff1b;对于大学学术交流论坛当然也不能排除在外&#xff0c;随着网络技术的不断成熟&#xff0c;带动了大学学术交流论坛的发展&#xff0c;它彻底…

构建 Java Web 应用程序:从 Servlet 到数据库交互(Eclipse使用JDBC连接Mysql数据库)

第 1 部分&#xff1a;环境设置 安装 Java Development Kit (JDK)&#xff1a;下载并安装 JDK。设置 IDE&#xff1a;安装并配置 IDE&#xff08;如 IntelliJ IDEA 或 Eclipse&#xff09;。安装数据库&#xff1a;下载并安装 MySQL 数据库。配置数据库&#xff1a;创建数据库…

C 语言面向对象

面向对象的基本特性&#xff1a;封装&#xff0c;继承&#xff0c;多态 1.0 面向过程概念 当我们在编写程序时&#xff0c;通常采用以下步骤&#xff1a; 1. 将问题的解法分解成若干步骤 2. 使用函数分别实现这些步骤 3. 依次调用这些函数 这种编程风格的被称作 面向过程…

aws服务--机密数据存储KMS(1)介绍和使用

在AWS(Amazon Web Services)中存储机密数据时,安全性和合规性是最重要的考虑因素。AWS 提供了多个服务和工具,帮助用户确保数据的安全性、机密性以及合规性。AWS Secrets Manager、KMS(Key Management Service)是推荐的存储机密数据的AWS服务和最佳实践。这里先看KMS。 …

ArcGIS应用指南:ArcGIS制作局部放大地图

在地理信息系统&#xff08;GIS&#xff09;中&#xff0c;制作详细且美观的地图是一项重要的技能。地图制作不仅仅是简单地将地理数据可视化&#xff0c;还需要考虑地图的可读性和美观性。局部放大图是一种常见的地图设计技巧&#xff0c;用于展示特定区域的详细信息&#xff…

【案例学习】如何使用Minitab实现包装过程的自动化和改进

Masimo 是一家全球性的医疗技术公司&#xff0c;致力于开发和生产各种行业领先的监控技术&#xff0c;包括创新的测量、传感器和患者监护仪。在 Masimo Hospital Automation 平台的助力下&#xff0c;Masimo 的连接、自动化、远程医疗和远程监控解决方案正在改善医院内外的护理…

【JavaEE初阶】多线程初阶下部

文章目录 前言一、volatile关键字volatile 能保证内存可见性 二、wait 和 notify2.1 wait()方法2.2 notify()方法2.3 notifyAll()方法2.4 wait 和 sleep 的对比&#xff08;面试题&#xff09; 三、多线程案例单例模式 四、总结-保证线程安全的思路五、对比线程和进程总结 前言…

【小白学机器学习33】 大数定律python的 pandas.Dataframe 和 pandas.Series基础内容

目录 0 总结 0.1pd.Dataframe有一个比较麻烦琐碎的地方&#xff0c;就是引号 和括号 0.2 pd.Dataframe关于括号的原则 0.3 分清楚几个数据类型和对应的方法的范围 0.4 几个数据结构的构造关系 list → np.array(list) → pd.Series(np.array)/pd.Dataframe 1 python 里…

《用Python画蔡徐坤:艺术与编程的结合》

简介 大家好&#xff01;今天带来一篇有趣的Python编程项目&#xff0c;用代码画出知名偶像蔡徐坤的形象。这个项目使用了Python的turtle库&#xff0c;通过简单的几何图形和精心设计的代码来展示艺术与编程的结合。 以下是完整的代码和效果介绍&#xff0c;快来试试看吧&…

OSG开发笔记(三十三):同时观察物体不同角度的多视图从相机技术

​若该文为原创文章&#xff0c;未经允许不得转载 本文章博客地址&#xff1a;https://blog.csdn.net/qq21497936/article/details/143932273 各位读者&#xff0c;知识无穷而人力有穷&#xff0c;要么改需求&#xff0c;要么找专业人士&#xff0c;要么自己研究 长沙红胖子Qt…

数据结构(Java版)第二期:包装类和泛型

目录 一、包装类 1.1. 基本类型和对应的包装类 1.2. 装箱和拆箱 1.3. 自动装箱和自动拆箱 二、泛型的概念 三、引出泛型 3.1. 语法规则 3.2. 泛型的优点 四、类型擦除 4.1. 擦除的机制 五、泛型的上界 5.1. 泛型的上界的定义 5.2. 语法规则 六、泛型方法 6.1…

ffmpeg 视频滤镜:高斯模糊-gblur

滤镜描述 gblur 官网地址 > FFmpeg Filters Documentation 这个滤镜会将视频变得模糊。 滤镜使用 参数 gblur AVOptions:sigma <float> ..FV.....T. set sigma (from 0 to 1024) (default 0.5)steps <int> ..FV.....T…

vue中路由缓存

vue中路由缓存 问题描述及截图解决思路关键代码及打印信息截图 问题描述及截图 在使用某一平台时发现当列表页码切换后点击某一卡片进入详情页后&#xff0c;再返回列表页时页面刷新了。这样用户每次看完详情回到列表页都得再重新输入自己的查询条件&#xff0c;或者切换分页到…

eclipse-git项目提示NO-HEAD

1、出现该问题的过程 本人在用eclipse拉取git代码&#xff0c;刚拉取完&#xff0c;可能还没来得及跟本地的分支合并&#xff0c;电脑就卡动了。无奈只能重启电脑&#xff0c;打开eclipse&#xff0c;maven项目后面就出现了xxx NO-HEAD的提示。 2、问题解决 根据错误提示&am…

网络安全与加密

1.Base64简单说明描述&#xff1a;Base64可以成为密码学的基石&#xff0c;非常重要。特点&#xff1a;可以将任意的二进制数据进行Base64编码结果&#xff1a;所有的数据都能被编码为并只用65个字符就能表示的文本文件。65字符&#xff1a;A~Z a~z 0~9 / 对文件进行base64编码…

goframe开发一个企业网站 在vue-next-admin 显示验证码 19

index.go 文件中的代码&#xff0c;我将为该文件中的主要功能和方法添加注释&#xff0c;并生成一篇 Markdown 格式的文章。这将包括对每个函数的用途、输入参数和返回值的简要说明。 index.go 包和导入 package adminimport ("context""errors""gf…

数据库的联合查询

数据库的联合查询 简介为什么要使⽤联合查询多表联合查询时MYSQL内部是如何进⾏计算的构造练习案例数据案例&#xff1a;⼀个完整的联合查询的过程 内连接语法⽰例 外连接语法 ⽰例⾃连接应⽤场景示例表连接练习 ⼦查询语法单⾏⼦查询多⾏⼦查询多列⼦查询在from⼦句中使⽤⼦查…