当前位置: 首页 > news >正文

【力扣 Hot100】 刷题日记

D3

128.最长连续序列

错解
class Solution {public int longestConsecutive(int[] nums) {Arrays.sort(nums);int maxCnt = 0;int cnt = 0;for (int i = 0; i < nums.length - 1; i++) {if(nums[i] != nums[i + 1] - 1){//如果不连续,取cnt与maxCnt较大值,cnt清零maxCnt = Math.max(cnt, maxCnt);cnt = 0;}else{cnt++;maxCnt = Math.max(cnt, maxCnt);}}return maxCnt = maxCnt != 0 ? maxCnt + 1 : maxCnt;}
}

这里我犯了一个错误,把连续理解为了,索引连续并且元素大小连续。事实上,题目中只需要保证元素大小连续即可,比如1 1 2 2 3,最大连续长度为3,最先想到的是用Treeset去重排序,但我看题目提示是哈希表。

TreeSet朴素解法

就是提供两个计数器,记录连续元素的长度以及最大长度,虽然是一次for循环就解决了,但是TreeSet的排序时间复杂度是O(log n),所以总体时间复杂度是O(nlogn),是不符合题意的。

class Solution {public int longestConsecutive(int[] nums) {int cnt = 1; //当前连续长度int maxCnt = 1; //Set<Integer> set = new TreeSet<>();for (int num : nums) {set.add(num);}if(set.isEmpty()) return 0;if(set.size() == 1) return 1;Iterator<Integer> it = set.iterator();int prev = it.next();while(it.hasNext()){int current = it.next();if(current != prev + 1){maxCnt = Math.max(maxCnt, cnt);cnt = 1;}else{cnt++;maxCnt = Math.max(maxCnt, cnt);}prev = current;}return maxCnt;}
}
HashSet解法

这种方法时间复杂度为O(n),符合题意。

思路:

使用set是为了保证元素不重复,降低时间复杂度,因为题目有说,不要求元素在原序列连续。如果集合中有元素x-1,那么最长长度一定是从x-1开始,比如数组1 2 4 6 7 8 9,如果有6,那么从6开始的序列最长长度就不会从7开始,所以只要统计出从某个元素开始的连续元素的最大值,某个元素到这个最大值的元素数目就是最大值。

代码如下:

class Solution {public int longestConsecutive(int[] nums) {Set<Integer> set = new HashSet<>();for(int num : nums){set.add(num);}int ans = 0;for(int x : set){if(set.contains(x-1)){//如果还有更小的连续元素,找最小元素continue;}int y = x + 1;while(set.contains(y)){y++;}ans = Math.max(ans, y - x);//获取最大元素长度}return ans;}}
http://www.lryc.cn/news/610721.html

相关文章:

  • Python分块读取大型Excel文件
  • 豆包新模型与 PromptPilot 实操体验测评,AI 辅助创作的新范式探索
  • LangGraph学习笔记 — LangGraph中State状态模式
  • 自动驾驶控制算法——MPC控制算法
  • qq scheme
  • GaussDB 并行创建索引
  • 使用iptables的nat链表进行端口转发
  • 基于MATLAB实现的频域模态参数识别方法
  • 算法3. 无重复字符的最长子串
  • Django中的转发与重定向详解
  • Boosting 知识点整理:机制、对比与应用场景
  • 统计鱼儿分布情况 Java
  • 复制网页文字到Word、WPS文字?选中后直接拖放
  • C语言线程同步详解(互斥锁、信号量、条件变量和读写锁)
  • Apache OFBiz Scrum 组件命令注入漏洞
  • FLAN-T5:大规模指令微调的统一语言模型框架
  • C++(线程)
  • 恶魔轮盘赌
  • Java Date类介绍
  • 前端保持和服务器时间同步的方法【使用vue3举例】
  • 利用m0改造循迹模块处理笔记00
  • 强光干扰下误报率↓82%!陌讯多模态融合算法在火焰识别的落地优化
  • 服务器数据恢复—坏道致Raid5阵列硬盘离线如何让数据重生?
  • Linux 系统启动原理2
  • 2025年服务器漏洞生存指南:从应急响应到长效免疫的实战框架
  • Pandas query() 方法详解
  • 防水防尘防摔性能很好的智能三防手机,还有22000mAh大电池
  • 手机通话检测数据集介绍-3,100 张图片 智能监控系统 驾驶安全监控
  • 联发科芯片组曝高危漏洞:越界写入缺陷危及智能手机与物联网设备安全
  • Tasks and Deadlines(Sorting and Searching)