数组：无序的整数类型数组，求最长的连续元素序列的长度。
发布时间
阅读量：
阅读量
给定一个无序的整数类型数组，求最长的连续元素序列的长度。
例如：
给出的数组为[100, 4, 200, 1, 3, 2],
最长的连续元素序列为[1, 2, 3, 4]. 返回这个序列的长度：4
你需要给出时间复杂度在O（n）之内的算法
给定一个无序的整数类型数组，求最长的连续元素序列的长度。
例如：
给出的数组为[100, 4, 200, 1, 3, 2],
最长的连续元素序列为[1, 2, 3, 4]. 返回这个序列的长度：4
你需要给出时间复杂度在O（n）之内的算法
//暴力算法o(n^3) 空间o(1)
class Solution {
private boolean arrayContains(int[] arr, int num) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == num) {
return true;
}
}
return false;
}
public int longestConsecutive(int[] nums) {
int longestStreak = 0;
for (int num : nums) {
int currentNum = num;
int currentStreak = 1;
while (arrayContains(nums, currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
return longestStreak;
}
}//排序o(nlogn)
import java.util.*;
public class Solution {
/** * * @param num int整型一维数组
* @return int整型
*/
9. //枚举每个数字作为序列的第一个数字
public int longestConsecutive (int[] num) {
if(num.length==0){
return 0;
}
//排序：1,2,2,3,4,5
Arrays.sort(num);
int longSteak=1;//最大排序序列个数
int currentSteak=1;
for(int i=1;i<num.length;i++){
if(num[i]!=num[i-1]){
if(num[i-1]==num[i]+1){
currentSteak+=1;
}else{
longSteak=Math.max(longSteak,currentSteak);//选择最大连续个数
currentSteak=1;//重新计数
}
}
}
return longSteak;
}
}Arrays.sort()相关的信息总结如下:
通用: super 类
策略设计模式(strategy pattern);
归并排序(merge sort): 时间复杂度 n*log(n);
//hashset o(1) 无序
import java.util.*;
public class Solution {
/** * * @param num int整型一维数组
* @return int整型
*/
public int longestConsecutive (int[] num) {
Set<Integer>set=new HashSet<>();
for(int n:num){
set.add(n);
}
int longSteak=1;
for(int n:num){
if(set.remove(n)){
int len=1;
int val=n;//记录n,
int smallnum=val-1;
int bignum=val+1;
while(set.remove(smallnum)){ //从前走，找到连续的就删除了，for循环不会再考虑它了
len++;
smallnum--;
}
while(set.remove(bignum)){ //从后走
len++;
bignum++;
}
longSteak=Math.max(longSteak,len);
}
}
return longSteak;
}
}全部评论 (0)
还没有任何评论哟~