企业网站建设自己的官网,网站建设及 维护合同,网站设计提案,企业邮箱怎么申请的128.给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1#xff1a; 输入#xff1a;nums [100,4,200,1,3,2] 输出#xff1a;4… 128.给定一个未排序的整数数组 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 这里就直接调 api 排序了排序后最长连续序列在数组中就一定为连续的整数了。设 dp[i] 为以 nums[i] 结尾的子数组的最长序列dp[i] 有两种情况当 nums[i]nums[i-1]1 表示它能和前一个数组成连续的序列就为 dp[i-1]1否则就没法连续 dp[i]1。初始情况也很好理解dp[0]1 表示长度为 1 的数组无论如何存在连续序列长度为 1。时间复杂度: O ( n ) O(n) O(n)空间复杂度: O ( n ) O(n) O(n) public int longestConsecutive(int[] nums) {int n nums.length;if(n 0)return 0;Arrays.sort(nums);// 由于 dp 更新时只和前一个结果有关所以不需要数组int dp 1;int ans dp;ListInteger list new ArrayList();// 去重你也可以用一个变量记录前一个数// 这样也就不需要 list 了空间复杂度将为 O(1)for(int i0;in;i){while(in-1 nums[i]nums[i1])i;list.add(nums[i]);}for(int i1;ilist.size();i){if(list.get(i)list.get(i-1)1)dp;else dp1;ansMath.max(ans,dp);}return ans;}去重优化 public int longestConsecutive(int[] nums) {int n nums.length;if(n 0)return 0;Arrays.sort(nums);int dp 0;int ans 0;int prenums[n-1]1;for(int i0;in;i){while(in-1 nums[i]nums[i1])i;if(nums[i]pre1)dp;else dp1;prenums[i];ansMath.max(ans,dp);}return ans;}还有用 set 递归暴力解的限定某个起点从 set 中找连续的序列长度很容易这里的计算用递归表示了。 SetInteger set new HashSet();public int longestConsecutive(int[] nums) {int n nums.length;int ans 0;if(n 0)return ans;// set 去重Arrays.stream(nums).forEach(v-{set.add(v);});for(int x:set){// 如果有 x-1 那从 x-1 开始的长度肯定更长所以跳过 xif(set.contains(x-1))continue;// 这就等于比较每个连续序列的长度ans Math.max(ans,dfs(x,0));}return ans;}// 计算从 x 开始的最长序列长度int dfs(int x,int res){if(set.contains(x))return dfs(x1,res1);else return res;}
