leetcode刷题（74）—128. 最长连续序列
leetcode刷题（74）—128. 最长连续序列
老马的编程之旅
发布于 2022-06-22 13:50:00
发布于 2022-06-22 13:50:00
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
方法 2：排序 想法
如果我们可以将数组中的数字升序迭代，找连续数字会变得十分容易。为了将数组变得有序，我们将数组进行排序。
算法 首先检查输入的数组是否为空数组，如果是，函数直接返回 0 。对于其他情况，我们将 nums 数组排序，并考虑除了第一个数字以外的每个数字与它前一个数字的关系。如果当前数字和前一个数字相等，那么我们当前的序列既不会增长也不会中断，我们只需要继续考虑下一个数字。如果不相等，我们必须要检查当前数字是否能延长答案序列（也就是 nums[i] == nums[i-1] + 1）。如果可以增长，那么我们将当前数字添加到当前序列并继续。否则，当前序列被中断，我们记录当前序列的长度并将序列长度重置为 1 。由于 nums 中的最后一个数字也可能是答案序列的一部分，所以我们将当前序列的长度和记录下来的最长序列的长度的较大值返回。
class Solution {
public static int longestConsecutive(int[] nums) {
if (nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int max = 1;
int count = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]){
continue;
}
if (nums[i] == nums[i - 1] + 1) {
count += 1;
} else {
count = 1;
}
max = Math.max(count, max);
}
return max;
}
}注意： 1.这里唯一需要注意的地方就是nums[i] == nums[i - 1]需要跳过，否则得出的答案会有误
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-05-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
