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

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

.net 8使用hangfire实现库存同步任务

C# 使用HangFire 第一章:.net Framework 4.6 WebAPI 使用Hangfire 第二章:net 8使用hangfire实现库存同步任务 文章目录 C# 使用HangFire前言项目源码一、项目架构二、项目服务介绍HangFire服务结构解析HangfireCollectionExtensions 类ModelHangfireSettingsHttpAuthInfoUs…

滑动窗口最大值(java)

题目描述 给你一个整数数组 nums&#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 示例 1&#xff1a; 输入&#xff1a;nums [1,3,-1,-3,5,3,6,7]…

springboot项目使用maven打包,第三方jar问题

springboot项目使用maven package打包为可执行jar后&#xff0c;第三方jar会被打包进去吗&#xff1f; 答案是肯定的。做了实验如下&#xff1a; 第三方jar的项目结构及jar包结构如下&#xff1a;&#xff08;该第三方jar采用的是maven工程&#xff0c;打包为普通jar&#xf…

常用Rust日志处理工具教程

在本文中&#xff0c;我想讨论Rust中的日志。通过一些背景信息&#xff0c;我将带您了解两个日志库&#xff1a;env_logger和log4rs。最后&#xff0c;我将分享我的建议和github的片段。 Rust log介绍 log包是Rust中日志API的事实标准&#xff0c;共有五个日志级别&#xff1…

嵌入式的C/C++:深入理解 static、const 与 volatile 的用法与特点

目录 一、static 1、static 修饰局部变量 2、 static 修饰全局变量 3、static 修饰函数 4、static 修饰类成员 5、小结 二、const 1、const 修饰普通变量 2、const 修饰指针 3、const 修饰函数参数 4. const 修饰函数返回值 5. const 修饰类成员 6. const 与 #defi…

时间请求参数、响应

&#xff08;7&#xff09;时间请求参数 1.默认格式转换 控制器 RequestMapping("/commonDate") ResponseBody public String commonDate(Date date){System.out.println("默认格式时间参数 date > "date);return "{module : commonDate}"; }…

SpringBoot(9)-Dubbo+Zookeeper

目录 一、了解分布式系统 二、RPC 三、Dubbo 四、SpringBootDubboZookeeper 4.1 框架搭建 4.2 实现RPC 一、了解分布式系统 分布式系统&#xff1a;由一组通过网络进行通信&#xff0c;为了完成共同的任务而协调工作的计算机节点组成的系统 二、RPC RPC&#xff1a;远程…

单片机学习笔记 8. 矩阵键盘按键检测

更多单片机学习笔记&#xff1a;单片机学习笔记 1. 点亮一个LED灯单片机学习笔记 2. LED灯闪烁单片机学习笔记 3. LED灯流水灯单片机学习笔记 4. 蜂鸣器滴~滴~滴~单片机学习笔记 5. 数码管静态显示单片机学习笔记 6. 数码管动态显示单片机学习笔记 7. 独立键盘 目录 0、实现的…

道品智能科技移动式水肥一体机:农业灌溉施肥的革新之选

在现代农业的发展进程中&#xff0c;科技的力量正日益凸显。其中&#xff0c;移动式水肥一体机以其独特的可移动性、智能化以及实现水肥一体化的卓越性能&#xff0c;成为了农业领域的一颗璀璨新星。它不仅改变了传统的农业灌溉施肥方式&#xff0c;更为农业生产带来了高效、精…

android 音效可视化--Visualizer

Visualizer 是使应用程序能够检索当前播放音频的一部分以进行可视化。它不是录音接口&#xff0c;仅返回部分低质量的音频内容。但是&#xff0c;为了保护某些音频数据的隐私&#xff0c;使用 Visualizer 需要 android.permission.RECORD_AUDIO权限。传递给构造函数的音频会话 …

计算机网络八股整理(一)

计算机网络八股文整理 一&#xff1a;网络模型 1&#xff1a;网络osi模型和tcp/ip模型分别介绍一下 osi模型是国际标准的网络模型&#xff0c;它由七层组成&#xff0c;从上到下分别是&#xff1a;应用层&#xff0c;表示层&#xff0c;会话层&#xff0c;传输层&#xff0c;…

利用Python爬虫获得1688按关键字搜索商品:技术解析

在电商领域&#xff0c;1688作为中国领先的B2B电商平台&#xff0c;其商品搜索功能对于商家来说具有极高的价值。通过获取搜索结果&#xff0c;商家可以更好地了解市场趋势&#xff0c;优化产品标题&#xff0c;提高搜索排名。本文将介绍如何使用Python编写爬虫&#xff0c;以获…

Spring Boot集成MyBatis-Plus:自定义拦截器实现动态表名切换

Spring Boot集成MyBatis-Plus&#xff1a;自定义拦截器实现动态表名切换 一、引言 介绍动态表名的场景需求&#xff0c;比如多租户系统、分表分库&#xff0c;或者不同业务模块共用一套代码但操作不同表。说明 MyBatis-Plus 默认绑定固定表名的问题。 二、项目配置 1. 集成 M…

(原创)Android Studio新老界面UI切换及老版本下载地址

前言 这两天下载了一个新版的Android Studio&#xff0c;发现整个界面都发生了很大改动&#xff1a; 新的界面的一些设置可参考一些博客&#xff1a; Android Studio新版UI常用设置 但是对于一些急着开发的小伙伴来说&#xff0c;没有时间去适应&#xff0c;那么怎么办呢&am…

数据新时代:如何选择现代数据治理平台(上)

谈现代数据治理系统的十大架构特征 最近一位老友找到我&#xff0c;咨询他的数据治理平台到底该不该换&#xff0c;背景是这样的&#xff1a;若干年前采购了一个市场主流的数据治理平台&#xff0c;功能大概就是数据治理三件套——标准、元数据和质量等经典数据治理的功能。现…

抖音SEO矩阵系统:开发技术分享

市场环境剖析 短视频SEO矩阵系统是一种策略&#xff0c;旨在通过不同平台上的多个账号建立联系&#xff0c;整合同一品牌下的各平台粉丝流量。该系统通过遵循每个平台的规则和内容要求&#xff0c;输出企业和品牌形象&#xff0c;以矩阵形式增强粉丝基础并提升商业价值。抖音作…

从零开始打造个人博客:我的网页设计之旅

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 ✨特色专栏&#xff1a…

STM32F103C8T6实时时钟RTC

目录 前言 一、RTC基本硬件结构 二、Unix时间戳 2.1 unix时间戳定义 2.2 时间戳与日历日期时间的转换 2.3 指针函数使用注意事项 ​三、RTC和BKP硬件结构 四、驱动代码解析 前言 STM32F103C8T6外部低速时钟LSE&#xff08;一般为32.768KHz&#xff09;用的引脚是PC14和PC…

Jmeter中的定时器

4&#xff09;定时器 1--固定定时器 功能特点 固定延迟&#xff1a;在每个请求之间添加固定的延迟时间。精确控制&#xff1a;可以精确控制请求的发送频率。简单易用&#xff1a;配置简单&#xff0c;易于理解和使用。 配置步骤 添加固定定时器 右键点击需要添加定时器的请求…

Fakelocation Server服务器/专业版 ubuntu

前言:需要Ubuntu系统 Fakelocation开源文件系统需求 Ubuntu | Fakelocation | 任务一 任务一 更新Ubuntu&#xff08;安装下载不再赘述&#xff09; sudo -i # 提权 sudo apt update # 更新软件包列表 sudo apt upgrade # 升级已安装的软…