相应式手机网站建设,微信开放平台的发展前景,wordpress图片后加载,招远专业做网站公司最长连续序列
给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。示例 1#xff1a;输入#xff1a;nums [100,4,200,1,3,2]输出#x…最长连续序列
给定一个未排序的整数数组 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
解题思路
首先将数组中的所有元素存入一个集合HashSet中方便进行快速查找。然后遍历数组中的每个元素对于每个元素检查其是否是一个序列的起始点即判断其前一个数是否在集合中存在。如果是起始点则从该点开始向后查找连续序列的长度直到找到序列的末尾。更新最长连续序列的长度并在遍历完成后返回结果。
具体步骤
将数组中的所有元素存入一个集合HashSet中。遍历数组中的每个元素对于每个元素执行以下步骤 判断当前元素是否是一个序列的起始点即判断其前一个数是否在集合中存在。如果是起始点则从该点开始向后查找连续序列的长度直到找到序列的末尾。更新最长连续序列的长度。 返回最长连续序列的长度。
java实现
public class LongestConsecutiveSequence {public int longestConsecutive(int[] nums) {if (nums null || nums.length 0) {return 0;}// 将数组元素放入 HashSet 中以便快速查找HashSetInteger numSet new HashSet();for (int num : nums) {numSet.add(num);}int longestStreak 0;// 遍历数组元素for (int num : nums) {// 如果当前元素是一个序列的起点即前一个数字不存在于 HashSet 中if (!numSet.contains(num - 1)) {int currentNum num;int currentStreak 1;// 继续查找连续的数字while (numSet.contains(currentNum 1)) {currentNum;currentStreak;}// 更新最长序列的长度longestStreak Math.max(longestStreak, currentStreak);}}return longestStreak;}public static void main(String[] args) {LongestConsecutiveSequence solution new LongestConsecutiveSequence();int[] nums1 {100, 4, 200, 1, 3, 2};System.out.println(solution.longestConsecutive(nums1)); // 输出4int[] nums2 {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};System.out.println(solution.longestConsecutive(nums2)); // 输出9}
}
