题目地址
https://leetcode.com/problems/longest-consecutive-sequence/description/
题目描述
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Accepted
200,786
Submissions
485,346
思路
这是一道最最长连续数字序列长度的题目, 官网给出的难度是hard
.
符合直觉的做法是先排序,然后用一个变量记录最大值,遍历去更新最大值即可,
代码:
if (nums.length === 0) return 0; let count = 1; let maxCount = 1; // 这里其实可以不需要排序,这么做只不过是为了方便理解 nums = [...new Set(nums)].sort((a, b) => a - b); for (let i = 0; i < nums.length - 1; i++) { if (nums[i + 1] - nums[i] === 1) { count++; } else { if (count > maxCount) { maxCount = count; } count = 1; } } return Math.max(count, maxCount);
但是需要排序时间复杂度会上升,题目要求时间复杂度为 O(n),
那么我们其实可以不用排序去解决的。
思路就是将之前”排序之后,通过比较前后元素是否相差 1 来判断是否连续“的思路改为
不排序而是直接遍历,然后在内部循环里面查找是否存在当前值的邻居元素
,但是马上有一个
问题,内部我们查找是否存在当前值的邻居元素
的过程如果使用数组时间复杂度是 O(n),
那么总体的复杂度就是 O(n^2),完全不可以接受。怎么办呢?
我们换个思路,用空间来换时间。比如用类似于 hashmap 这样的数据结构优化查询部分,将时间复杂度降低到 O(1), 代码见后面代码部分
关键点解析
- 空间换时间
代码
/* * @lc app=leetcode id=128 lang=javascript * * [128] Longest Consecutive Sequence * * https://leetcode.com/problems/longest-consecutive-sequence/description/ * * algorithms * Hard (40.98%) * Total Accepted: 200.3K * Total Submissions: 484.5K * Testcase Example: '[100,4,200,1,3,2]' * * Given an unsorted array of integers, find the length of the longest * consecutive elements sequence. * * Your algorithm should run in O(n) complexity. * * Example: * * * Input: [100, 4, 200, 1, 3, 2] * Output: 4 * Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. * Therefore its length is 4. * * */ /** * @param {number[]} nums * @return {number} */ var longestConsecutive = function(nums) { nums = new Set(nums); let max = 0; let y = 0; nums.forEach(x => { // 说明x是连续序列的开头元素 if (!nums.has(x - 1)) { y = x + 1; while (nums.has(y)) { y = y + 1; } max = Math.max(max, y - x); // y - x 就是从x开始到最后有多少连续的数字 } }); return max; };LeetCode题解1218.longest-arithmetic-subsequence-of-given-difference
题目地址 https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/ 题目描述 给你一个整数数组 arr 和一个整数 difference,请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列,并返回其中最长的等差子序…
LeetCode题解堆排序和快速排序堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法,其中 n 为数据规模。 那么两者谁更快呢? 为什么?题解:快排最坏情况下是O(n^2),平均和最好是O(nlogn) ,堆排序始终为O(nlogn),还是堆排序快吧
LeetCode题解斜着遍历遍历是算法的基础。 我们平时看到的 DFS 和 BFS 都是搜索, 而搜索的核心就是遍历,而关键点就是遍历的方式。 从根本上说动态规划也是枚举所有的可能,而枚举就需要用到遍历。 而平时遍历一个二维数组 martrix 的时候, 我们习惯的方式是按行从左到右或者从右到左遍历。 少有情况是按照列遍历, 更少有情况是斜着遍历。那么这次就考考你, 怎么斜着遍历一个二…
LeetCode题解砝码的最小数量假设有三种重量的砝码,2g、3g、7g,对于任意重量物品,请设计一个函数getResult(weight),接收一个参数weight,返回所需砝码的最小数量。输入示例:const weight = 100;输出示例:getResult(weight) // 15 其中7g的14个,2g的1个题解:```phpfunction getResult($weigh…
LeetCode题解93. 复原IP地址给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成),整数之间用 '.' 分隔。 示例:输入: \"25525511135\"输出: [\"255.255.11.135\", \"255.255.111.35\"]来源:力扣(LeetCode)链接:https://le…