【LeeCode】128. 最长连续序列
相关标签： # java# java
【题目描述】
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题
【示例】
【代码】admin
思路参考 传闻
package com.company;
import java.util.*;
// 2022-12-26
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0 ) return 0;
if (nums.length == 1 ) return 1;
// 数组排序
Arrays.sort(nums);
int current = 1;
int max = 1;
for (int i = 1; i < nums.length; i++){
if (nums[i -1] == nums[i]) continue;
if (nums[i] - nums[i - 1] == 1){
current++;
max = Math.max(current, max);
}else {
current = 1;
}
}
return max;
}
}
public class Test{
public static void main(String[] args) {
int[] arr = { 100,4,200,1,3,2 };
// new Solution().longestConsecutive(arr); // 输出 4
System.out.println("-----------------------------------");
int[] arr1 = { 0,3,7,2,5,8,4,6,0,1 }; // 输出 9
new Solution().longestConsecutive(arr1);
System.out.println("-----------------------------------");
int[] arr2 = { 0, 0,-1};
new Solution().longestConsecutive(arr2); // 输出 2
}
}
【代码】官方
个人理解： 由于我们要枚举的数 x 一定是在数组中不存在前驱数 x−1 的, 如果不存在 则从 x 开始累加进行判断
package com.company;
import javax.swing.plaf.synth.SynthOptionPaneUI;
import java.util.*;
import java.util.stream.Collectors;
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<Integer>();
for (int num : nums) {
num_set.add(num);
}
int longestStreak = 0;
for (int num : num_set) {
if (!num_set.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (num_set.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
System.out.println(longestStreak);
return longestStreak;
}
}
public class Test{
public static void main(String[] args) {
int[] arr = { 100,4,200,1,3,2 };
new Solution().longestConsecutive(arr); // 输出 4
System.out.println("-----------------------------------");
int[] arr1 = { 0,3,7,2,5,8,4,6,0,1 }; // 输出 9
new Solution().longestConsecutive(arr1);
System.out.println("-----------------------------------");
int[] arr2 = { 0, 0,-1};
new Solution().longestConsecutive(arr2); // 输出 2
System.out.println("-----------------------------------");
int[] arr3 = {9,1,-3,2,4,8,3,-1,6,-2,-4,7};
new Solution().longestConsecutive(arr3); // 输出 4
System.out.println("-----------------------------------");
int[] arr4 = {4,0,-4,-2,2,5,2,0,-8,-8,-8,-8,-1,7,4,5,5,-4,6,6,-3};
new Solution().longestConsecutive(arr4); // 输出 5
}
}
【代码】admin
测试用例通过: 69/72 超时了
思路： 首先利用set去重, 同时利用treeSet进行key的排序 然后判断set中是否包含 key + 1 如果有则 count++ 否则count = 1
package com.company;
import javax.swing.plaf.synth.SynthOptionPaneUI;
import java.util.*;
import java.util.stream.Collectors;
// 2022-12-26
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0 ) return 0;
if (nums.length == 1 ) return 1;
Arrays.sort(nums);
Set<Integer> set = new TreeSet<>();
for (int x : nums){
set.add(x);
}
List<Integer> collect = set.stream().collect(Collectors.toList());
int count = 1;
int max = 1;
for (int i = 0; i < collect.size(); i++) {
int pre = collect.get(i);
int next = pre + 1;
if (collect.contains(next) && collect.indexOf(next) > i){
count++;
max = Math.max(count, max);
}else {
count = 1;
}
}
System.out.println(max);
return max;
}
}
public class Test{
public static void main(String[] args) {
int[] arr = { 100,4,200,1,3,2 };
new Solution().longestConsecutive(arr); // 输出 4
System.out.println("-----------------------------------");
int[] arr1 = { 0,3,7,2,5,8,4,6,0,1 }; // 输出 9
new Solution().longestConsecutive(arr1);
System.out.println("-----------------------------------");
int[] arr2 = { 0, 0,-1};
new Solution().longestConsecutive(arr2); // 输出 2
System.out.println("-----------------------------------");
int[] arr3 = {9,1,-3,2,4,8,3,-1,6,-2,-4,7};
new Solution().longestConsecutive(arr3); // 输出 4
System.out.println("-----------------------------------");
int[] arr4 = {4,0,-4,-2,2,5,2,0,-8,-8,-8,-8,-1,7,4,5,5,-4,6,6,-3};
new Solution().longestConsecutive(arr4); // 输出 5
}
}
文章来源： https://blog.51cto.com/u_13682316/5971148
特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。
举报
