前言
又是好久没有更新了
正文
问题来源
本问题来自leetcode上的128题。
问题描述
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例 1:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4
分析：
题目提示是并查集，于是就按并查集的想法来做：
首先每个数字是个单独一个集合，如果两个数相差为一则认为是同一个集合。
每个数字初始化情况leader指向自身，并且这个集合类的总数为1；若一个数与存在另外一个数绝对值相差只为1，则这个数需要融入另外一个数的集合内；若一个数与存在相差为1并且为-1的数，这个数和这两个数所在的集合要合并在一起；如何判断是在同一个集合，该数字leader（或者递归）指向同一个数。
type Node struct {
Leader int
Count int
}
func findLeader(m map[int]*Node, f int) (int,bool) {
Lnode, ok := m[f]
if !ok {
return 0, false
}
if f == Lnode.Leader {
return f, true
}
return findLeader(m, m[f].Leader)
}
func longestConsecutive(nums []int) int {
m := make(map[int]*Node)
max := 0
for _, i := range nums {
if _, ok := m[i]; ok {
continue
}
v1, ok1 := findLeader(m, i-1)
v2, ok2 := findLeader(m, i+1)
if ok1 {
if ok2 {
m[v1].Count += m[v2].Count + 1
m[v2].Leader = v1
m[i] = &Node{Leader:v1, Count:0}
if max < m[v1].Count {
max = m[v1].Count
}
} else {
m[v1].Count += 1
m[i] = &Node{Leader:v1, Count:0}
if max < m[v1].Count {
max = m[v1].Count
}
}
} else {
if ok2 {
m[v2].Count += 1
if max < m[v2].Count {
max = m[v2].Count
}
m[i] = &Node{Leader:v2, Count:0}
} else {
m[i] = &Node{Leader:i, Count:1}
if max < 1 {
max = 1
}
}
}
}
//fmt.Println(m)
return max
}
其他人的解法一
public class Solution {
public int longestConsecutive(int[] nums) {
int res = 0;
Set<Integer> s = new HashSet<Integer>();
for (int num : nums) s.add(num);
for (int num : nums) {
if (s.remove(num)) {
int pre = num - 1, next = num + 1;
while (s.remove(pre)) --pre;
while (s.remove(next)) ++next;
res = Math.max(res, next - pre - 1);
}
}
return res;
}
}
其他人的解法二
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int res = 0;
unordered_map<int, int> m;
for (int num : nums) {
if (m.count(num)) continue;
int left = m.count(num - 1) ? m[num - 1] : 0;
int right = m.count(num + 1) ? m[num + 1] : 0;
int sum = left + right + 1;
m[num] = sum;
res = max(res, sum);
m[num - left] = sum;
m[num + right] = sum;
}
return res;
}
};
总结：
勤思考。
结语
不管怎么样好好加油。
