重庆电商网站建设费用,服装网站建设进度及实施过程,网站改版原因,无极县最新招聘信息【问题描述】[困难]
给定一个未排序的整数数组#xff0c;找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。示例:输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。【解答思路】
1. SortCompare 先排序#xff0c;题意要求连…【问题描述】[困难]
给定一个未排序的整数数组找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。示例:输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
【解答思路】
1. SortCompare 先排序题意要求连续序列即可以比较nums[i]与 nums[i - 1]如果不相等表示是递增的趋势相等则反之递增后需要判断是否连续即相邻的元素差值是否为1 下面的代码处理边界casecase 如[-1,0][−1,0],不会比较max与cur的值需要在最后一道防线拦截一次
时间复杂度O(NlogN) 空间复杂度O(1) public int longestConsecutive(int[] nums) {if (nums null || nums.length 0) return 0;Arrays.sort(nums);int n nums.length;int max 1, cur 1;for (int i 1; i n; i) {if (nums[i] ! nums[i - 1]) {if (nums[i - 1] 1 nums[i]) cur;else {max Math.max(max, cur);cur 1;}}}return Math.max(max, cur);}
2. Hash 时间复杂度O(N) 空间复杂度O(1) public int longestConsecutive(int[] nums) {SetInteger set new HashSet();for (int num : nums) set.add(num);int max 0;for (int num : nums) {if (!set.contains(num - 1)) {//判断set不包含当前元素-1的值跳过已经计算的最长递增序列int curNum num;int curCnt 1;while (set.contains(curNum 1)) {curNum 1;curCnt 1;}max Math.max(max,curCnt);}}return max;}
【总结】
1.极小过渡到最大最大过渡到极小
2.暴力优化到最佳结果
转载链接https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/dong-tai-gui-hua-jie-zui-chang-zi-xu-lie-zi-chua-5/
