深圳私人网站优化,wordpress表单,贵州建设厅报名登录网站,广东成都网站建设推广公司LeetCode 128. 最长连续序列
题目描述
给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例#xff1a; 输入#xff1a;nums [10…LeetCode 128. 最长连续序列
题目描述
给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 输入nums [100,4,200,1,3,2] 输出4 解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
思路
用一个Set将输入数组里的元素全部存起来遍历这个Set的Iterator如果!set.contains(i-1)就开始计算序列长度之所以要做这个判断是因为如果set.contains(i-1)的话可以避免重复计算计算序列长度的方法是使用while循环条件为set.contains(i1)则当前序列长度i直到set中不再包含连续的数字时结束。最后比较这次计算的序列长度和最长序列长度得到最终结果maxMath.max(cur_count, max);
代码
class Solution {public int longestConsecutive(int[] nums) {SetInteger set new HashSet();for (int num : nums) {set.add(num);}int max 0;IteratorInteger iterator set.iterator();while (iterator.hasNext()) {int i iterator.next();if (!set.contains(i-1)){int cur_count 1;while (set.contains(i1)){cur_count;i;}max Math.max(cur_count, max);}}return max;}
}
