给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）
数据范围： 
，数组中的值满足 
要求：空间复杂度 )
，时间复杂度 )
[编程题]数组中的最长连续子序列
import java.util.*;
/**
* NC95 数组中的最长连续子序列
* @author d3y1
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* max increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型
*/
public int MLS (int[] arr) {
// return solution1(arr);
// return solution2(arr);
// return solution3(arr);
// return solution4(arr);
return solution5(arr);
}
/**
* 小根堆
* @param arr
* @return
*/
private int solution1(int[] arr){
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(int num: arr){
minHeap.offer(num);
}
int result = 0;
int len = 1;
int pre = minHeap.poll();
int cur;
while(!minHeap.isEmpty()){
cur = minHeap.poll();
if(cur == pre){
continue;
}
else if(cur == pre+1){
len++;
result = Math.max(result, len);
pre = cur;
}
else{
len = 1;
pre = cur;
}
}
return result;
}
/**
* 排序
* @param arr
* @return
*/
private int solution2(int[] arr){
int n = arr.length;
Arrays.sort(arr);
int result = 0;
int len = 1;
for(int i=0; i+1<n; i++){
if(arr[i+1] == arr[i]){
continue;
}
else if(arr[i+1] == arr[i]+1){
len++;
result = Math.max(result, len);
}
else{
len = 1;
}
}
return result;
}
/**
* HashSet
* @param arr
* @return
*/
private int solution3(int[] arr){
HashSet<Integer> set = new HashSet<>();
for(int num: arr){
set.add(num);
}
int result = 0;
int len;
for(int num: arr){
if(set.contains(num-1)){
continue;
}
int start = num;
len = 1;
while(set.contains(++start)){
len++;
}
result = Math.max(result, len);
}
return result;
}
/**
* HashMap
* @param arr
* @return
*/
private int solution4(int[] arr){
HashMap<Integer, Integer> map = new HashMap<>();
int result = 0;
int leftLen,rightLen,curLen;
for(int num: arr){
if(!map.containsKey(num)){
leftLen = map.getOrDefault(num-1, 0);
rightLen = map.getOrDefault(num+1, 0);
curLen = leftLen+1+rightLen;
map.put(num, curLen);
result = Math.max(result, curLen);
map.put(num-leftLen, curLen);
map.put(num+rightLen, curLen);
}
}
return result;
}
/**
* 并查集
* @param arr
* @return
*/
private int solution5(int[] arr){
UnionFind uf = new UnionFind(arr);
HashSet<Integer> set = new HashSet<>();
for(int num: arr){
set.add(num);
}
for(int num: arr){
if(set.contains(num-1)){
uf.union(num, num-1);
}
}
return uf.maxSize();
}
private class UnionFind {
int size;
HashMap<Integer, Integer> parent = new HashMap<>();
HashMap<Integer, Integer> sizeMap = new HashMap<>();
UnionFind(int[] nums){
this.size = 0;
for(int num: nums){
parent.put(num, num);
sizeMap.put(num, 1);
}
}
int find(int x){
int par = parent.get(x);
while(x != par){
parent.put(x, parent.get(par));
x = par;
par = parent.get(x);
}
return x;
}
void union(int p, int q){
int rootP = find(p);
int rootQ = find(q);
if(rootP != rootQ){
int unionSize = sizeMap.get(rootP)+sizeMap.get(rootQ);
if(rootP < rootQ){
parent.put(rootP, rootQ);
sizeMap.put(rootQ, unionSize);
}else{
parent.put(rootQ, rootP);
sizeMap.put(rootP, unionSize);
}
this.size = Math.max(size, unionSize);
}
}
int maxSize(){
return this.size;
}
}
}
发表于 2025-02-24 13:42:43
回复(0)
public int MLS (int[] arr) {
// write code here
Arrays.sort(arr);
int res=0;
for(int i=0;i<arr.length;i++){
int num=1;
while(i+1<arr.length && arr[i+1]-arr[i]<=1){
if(arr[i]+1==arr[i+1]){
num++;
}
i++;
}
res=Math.max(res,num);
}
return res;
}
发表于 2024-03-09 16:30:26
回复(0)
import java.util.*;
public class Solution {
/**
* max increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型
*/
//1 2 3 4 100 200
public int MLS (int[] arr) {
// write code here
Arrays.sort(arr);
int max=1;
int count=1;
for(int i=1;i<arr.length;i++){
if(arr[i]==arr[i-1]){
continue;
}
if(arr[i]-arr[i-1]==1){
count++;
}else{
count=1;
}
max=Math.max(count,max);
}
return max;
}
}
发表于 2023-05-14 15:53:50
回复(0)
//运行时间：343ms 占用内存：117184KB
import java.util.*;
public class Solution {
/**
* max increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型
*/
public int MLS (int[] arr) {
// write code here
int count=0;
int ans=0;
boolean has[]=new boolean[100000006];
for(int i=0;i<arr.length;i++){has[arr[i]]=true;}
for(int i=1;i<=100000;i++){
if(has[i]){count++;}
else{
ans=Math.max(ans,count);
count=0;
}
}
return Math.max(ans,count);
}
}
发表于 2021-12-29 14:10:13
回复(0)
public int MLS (int[] arr) {
// write code here
Arrays.sort(arr);
int max = 0;
int count = 0;
for(int i=0;i<arr.length;i++){
count = 1;
while(i+1<arr.length){
if(arr[i+1]==arr[i]+1)
count++;
else if(arr[i+1]!=arr[i])
break;
i++;
}
max = Math.max(max,count);
}
return max;
}
发表于 2021-11-26 16:16:38
回复(0)
// 换个方向，不连续的时候记录，代码会简单许多
public int MLS (int[] arr) {
int ans = 0;
Arrays.sort(arr);
int l = 0;
int repeat = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] == arr[i - 1]) {
repeat++;
continue;
}
if (arr[i] != arr[i - 1] + 1) {
ans = Math.max(ans, i - l - repeat);
l = i;
repeat = 0;
}
}
// 最后一个元素
if (l != arr.length - 1) {
ans = Math.max(ans, arr.length - l - repeat);
}
return ans;
}
发表于 2021-11-07 16:00:49
回复(0)
java
1.首先对数组进行排序（快排：O(nlogn)）；
2.使用map记录每个元素的位置，map的value值取List<Integer>是因为数组中有重复值
3.动态规划使用dp[i]表示以arr[i]为结尾的元素所能表示的最长连续子序列的长度，通过前面的map可以得到arr[i]-1对应的下标（如果数组中存在arr[i]-1,假设下标为index），那么dp[i]可以通过dp[i] = dp[index]+1获得
4.数组中的最长连续子序列长度为dp[i]的最大值
import java.util.*;
public class Solution {
/**
* max increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型
*/
public int MLS (int[] arr) {
// write code here
// 先对arr排序
Arrays.sort(arr);
// <arr[i], {index1,index2...}> // 存在值相同的情况
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
int len = arr.length;
for(int i=0;i<len;i++){
int num = arr[i];
if(map.keySet().contains(num)){
map.get(num).add(i);
}else{
List<Integer> list = new ArrayList<Integer>();
list.add(i);
map.put(num, list);
}
}
if(len == 0) return 0;
int max = 1;
// dp[i] 表示以arr[i]为结尾的元素所能表示最长连续子序列长度
int[] dp = new int[len];
// 初始时，每个arr[i]结尾的元素所能表示的最长连续子序列长度为1
Arrays.fill(dp,1);
for(int i=1;i<len;i++){
int curValue = arr[i];
if(map.keySet().contains(curValue-1)){
List<Integer> indexList = map.get(curValue-1);
for(int index : indexList){
dp[i] = Math.max(dp[index]+1,dp[i]);
}
max = Math.max(max, dp[i]);
}
}
return max;
}
}
发表于 2021-10-12 21:26:29
回复(0)
public class Solution {
/**
* max increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型
*/
public int MLS (int[] arr) {
// write code here
Arrays.sort(arr);
int max = 1,len = 1;
for (int i = 1; i < arr.length; i++) {
if (arr[i]==arr[i-1]) continue;
if (arr[i]==arr[i-1]+1) len++;
else len = 1;
max = Math.max(max,len);
}
return max;
}
}
发表于 2021-09-05 11:30:16
回复(1)
//手动去重+排序
import java.util.*;
public class Solution {
/**
* max increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型
*/
public int MLS (int[] arr) {
// write code here
if(arr.length==1)
return 1;
int len;
int res=0;
Arrays.sort(arr);
int i=1;
while(i<arr.length){
len=1;
if(arr[i]==arr[i-1]+1){
while(i<arr.length&&arr[i]==arr[i-1]+1){
i++;
len++;
while(i<arr.length&&arr[i]==arr[i-1])
i++;
}
}
else
i++;
res=Math.max(res,len);
}
return res;
}
}
发表于 2021-08-24 12:48:29
回复(0)
需要去重吗？排序，遇到相等的啥都不做不就行了。
import java.util.*;
public class Solution {
/**
* max increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型
*/
public int MLS (int[] arr) {
// write code here
Arrays.sort(arr);
int res = 0;
int cnt = 1;
for(int i=0;i<arr.length-1;i++){
if(arr[i+1]-arr[i]==1){
cnt++;
if(cnt>res){
res = cnt;
}
}else if(arr[i+1]==arr[i]){
continue;
}else{
cnt = 1;
}
}
return res;
}
}
发表于 2021-08-12 19:05:05
回复(0)
public class Solution {
/**
* max increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型
*/
public int MLS (int[] arr) {
// write code here
Set<Integer> set = new HashSet<>();
for (int t : arr) set.add(t);
int max = Integer.MIN_VALUE;
for (int t : arr) {
if (set.contains(t - 1)) continue;
int len = 1;
while (set.contains(++t)) len++;
max = Math.max(max, len);
}
return max;
}
}
发表于 2021-07-31 10:41:28
回复(0)
问题信息
难度：
31条回答
314收藏
8190浏览
通过挑战的用户
查看代码-
2023-02-26 11:08:58
-
2022-10-22 11:54:53 -
2022-09-18 08:03:44 -
2022-09-16 09:50:44
-
2022-09-14 14:14:23
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
