方法1：排序
方法2：Set
方法3：哈希表
方法4：并查集
解法1：排序+统计
排序数组
统计连续序列长度：遇到重复元素跳过；遇到不连续元素重置；遇到连续元素加一并更新max
import java.util.*; public class Solution { /** * max increasing subsequence * @param arr int整型一维数组 the array * @return int整型 */ public int MLS (int[] arr) { if(arr == null || arr.length == 0){ return 0; } int len = arr.length; Arrays.sort(arr); int count = 1; int result = 1; for(int i=0;i<len-1;i++){ if(arr[i+1] - arr[i] == 1){ count++; }else if(arr[i+1] - arr[i] == 0){ continue; }else{ count = 1; } result = Math.max(count, result); } return result; } }
解法2：使用set集合
准备一个HashSet，将所有元素入set，之后遍历数组中的每一个数num
- 如果num - 1存在于set中，那么num不可能是左边界，直接跳过
- 如果num - 1不存在于set中，那么num会是一个左边界，我们再不断地查找num+1、num+2......是否存在于set中，来看以num为左边界的连续序列能有多长
在上述遍历中，我们知道了对于每一个可能的左边界，能扩出的最长连续序列的长度，再在这些长度中取最大即为结果。
时间复杂度：O(n)，其中 n 为数组的长度。
外层循环需要 O(n)的时间复杂度，只有当一个数是连续序列的第一个数的情况下才会进入内层循环，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。根据上述分析可知，总时间复杂度为 O(n)空间复杂度：O(n)。哈希表存储数组中所有的数需要 O(n) 的空间
import java.util.*; public class Solution { public int MLS (int[] arr) { if(arr.length == 0) return 0; int n = arr.length; int max = 1; Set<Integer> set = new HashSet<>(); for(int num:arr) set.add(num); //先将数组中的值都存储在set集合中 for(int num:arr){ if(set.contains(num-1)) continue; //如果集合中包含比当前值小1的，则结束本次循环 int start = num; //不存在比当前值小1的，则去寻找以当前值开始的连续子序列 while(set.contains(start+1)){ start++; } //得到较长的子序列 max = Math.max(max,start-num+1); } return max; } }解法3：哈希表
哈希表的value存什么
- key存数字，value存什么？
- 新存入的数字，如果它找到相邻的数，它希望从邻居数那里获取什么信息？
- 很显然它希望，左邻居告诉它左边能提供的连续长度，右邻居告诉它右边能提供的连续长度
- 加上它自己的长度，就有了自己处在的连续序列的长度
更新新序列的两端数字的value - 同处一个连续序列的数字的value理应都相同，这是它们共同特征
- 但没有必要每个的value都是序列长度，只需要两端的数存序列的长度就好
- 因为靠的是两端和新数对接，序列是连续的，中间没有空位
- 序列的一端找到邻居后，将另一端对应的value更新为最新的序列长度
public int MLS (int[] arr) { HashMap<Integer, Integer> map = new HashMap<>(); int max = 0; for(int num : arr) { if(!map.containsKey(num)) { int preLen = map.get(num-1) == null ? 0 : map.get(num-1); int nextLen = map.get(num+1) == null ? 0 : map.get(num+1); int curLen = preLen + 1 + nextLen; map.put(num, curLen); max = Math.max(max, curLen); map.put(num - preLen, curLen); map.put(num + nextLen, curLen); } } return max; }
解法4：并查集
链接：https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/javacong-bao-li-fa-dao-zi-shang-er-xia-dong-tai-gu/
用并查集的话，就是每次union的时候，更新子树size，每次更新也更新最大值len，union到最后一个元素后，就能返回答案了
class Solution {
Set<Integer> checkInNums = new HashSet<>();
class UF {
// 记录树的“重量”
private int maxValue = 1;
// 存储⼀棵树
private Map<Integer, Integer> parent = new HashMap<>();
private Map<Integer, Integer> size = new HashMap<>();
public UF(int[] nums) {
for (int i = 0; i < nums.length; i++) {
parent.put(nums[i], nums[i]);
size.put(nums[i], 1);
}
}
public void union(int p, int q) {
if(!checkInNums.contains(p) || !checkInNums.contains(q))
return;
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
// ⼩树接到⼤树下⾯，较平衡
if (size.get(rootP) > size.get(rootQ)) {
parent.put(rootQ, rootP);
size.put(rootP, size.get(rootP)+size.get(rootQ));
maxValue = Math.max(maxValue, size.get(rootP));
}
else {
parent.put(rootP, rootQ);
size.put(rootQ, size.get(rootP)+size.get(rootQ));
maxValue = Math.max(maxValue, size.get(rootQ));
}
}
private int find(int x) {
while (parent.get(x) != x) {
int tmp = parent.get(x);
//进⾏路径压缩
parent.put(x, parent.get(tmp));
x = tmp;
}
return x;
}
public int findMax() {
return maxValue;
}
}
public int longestConsecutive(int[] nums) {
if(nums.length == 0)
return 0;
UF uf = new UF(nums);
for(int i = 0; i < nums.length; i++)
checkInNums.add(nums[i]);
for(int i = 0; i < nums.length; i++)
uf.union(nums[i], nums[i]-1);
return uf.findMax();
}
}
京公网安备 11010502036488号