企业网站推广名词解释,企业网站 备案,wordpress主题根目录,成都定制公交appLeetCode哈希表#xff1a;最长连续序列
题目描述
给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1#xff1a;
输入最长连续序列
题目描述
给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1
输入nums [100,4,200,1,3,2]
输出4
解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2
输入nums [0,3,7,2,5,8,4,6,0,1]
输出9解题思路
首先想到的方法就是先排序然后再找到符合条件序列但这样的话复杂度就不符合题目要求。最好的排序的是nlogn因此排序这条路走不通考虑采用哈希哈希的一个优点就是寻找元素容易那就考虑怎么去找这个元素两种方案
第一种找到一个序列最小值再以此向大的进行判断第二种找到一个序列最大的向小的方向判断
最后再返回最长长度
步骤如下
创建HashSet首先创建一个HashSet用于存储数组中的元素。HashSet的目的是为了快速检查数组中是否包含某个元素以及在O(1)时间内添加元素。将数组元素加入HashSet遍历输入数组nums将每个元素加入HashSet。寻找连续序列对于每个元素num检查是否存在num - 1如果不存在说明num可能是一个连续序列的起点。然后从num开始通过不断检查num 1是否在HashSet中来找到连续序列的长度。更新最长连续序列的长度在每次找到一个连续序列后更新最长连续序列的长度。返回结果返回最终找到的最长连续序列的长度。
代码
public class hash2 {public int longestConsecutive(int[] nums) {HashSetInteger setnew HashSet();for (int num : nums) {set.add(num);}int ans0;for (int num : set) {int rightnum;if (!set.contains(right - 1)) {while (set.contains(right1))right;}ansMath.max(ans,right-num1);}return ans;}public static void main(String[] args) {hash2 hanew hash2();System.out.println(ha.longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}));}
}优化以及其他思想的方法
方法1 哈希集合最普遍也最简单的思路必须掌握方法2 哈希表思路1的进阶方法3 动态规划极其巧妙推荐掌握方法4 并查集建议掌握
传送迪迦~~
