算法-面试-最长连续序列

逃离我推掉我的手 2023-02-16 01:47 116阅读 0赞

# 算法-面试-最长连续序列 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/longest-consecutive-sequence/

## 1.2 题目描述 ##

给定一个未排序的整数数组，找出最长连续(等差为1)序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: \[100, 4, 200, 1, 3, 2\]  
输出: 4  
解释: 最长连续序列是 \[1, 2, 3, 4\]。它的长度为 4。

# 2 并查集 #

## 2.1 思路 ##

遍历每个数字，如果小1或大1的数字存在，就进行并查集join。

最后遍历所有祖先，找出并查集最大的那个。

## 2.2 代码 ##

class Solution { 
        // 过滤重复数字
        private Set<Integer> records = new HashSet<>();
        // 并查集，key为数字本身，value为他的parent
        Map<Integer, Integer> unionFindSet = new HashMap<>();
        
        public int longestConsecutive(int[] nums) { 
            int result = 0;
            if(nums == null || nums.length == 0){ 
                return result;
            }
            
            for(int i = 0; i < nums.length; i++){ 
                // 过滤重复数字
                if(records.contains(nums[i])){ 
                    continue;
                }
                records.add(nums[i]);
                // 每个数最开始parent就是自己
                unionFindSet.put(nums[i], nums[i]);
                // 和小1的数字并查集Join
                int prev = nums[i] - 1;
                if(unionFindSet.containsKey(prev)){ 
                    join(nums[i], prev);
                }
                // 和大1的数字并查集Join
                int next = nums[i] + 1;
                if(unionFindSet.containsKey(next)){ 
                    join(nums[i], next);
                }
            }
            // 统计每个并查集元素个数
            Map<Integer, Integer> cntMap = new HashMap<>();
            for(int record : records){ 
                int root = find(record);
                Integer cnt = cntMap.get(root);
                int tmp = 0;
                if(cnt != null){ 
                    tmp = cnt + 1;
                }else{ 
                    tmp = 1;
                }
                cntMap.put(root, tmp);
                // 输出并查集元素最多的那个
                result = Math.max(result, tmp);
            }
            return result;
        }
    
        private void join(int p, int q){ 
            int left = find(p);
            int right = find(q);
            if(left == right){ 
                return;
            }
            unionFindSet.put(left, right);
        }
    
        private int find(int p){ 
            int son = p;
            while(unionFindSet.get(p) != p){ 
                p = unionFindSet.get(p);
            }
            while(unionFindSet.get(son) != son){ 
                int tmp = unionFindSet.get(son);
                unionFindSet.put(son, p);
                son = tmp;
            }
            return p;
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][20200607121523449.png]

## 2.4 空间复杂度 ##

O(N)

# 3 两趟遍历-两个方向延伸 #

## 3.1 思路 ##

前面并查集方法耗时太长，主要是join时每次需要一直往上查询直到root，还需要路径压缩。

其实我们简单考虑，要找到连续序列，无非就是当遇到数字i时，分别找i-1, i-2, i-3, … 以及 i+1, i+2, i+3…，并将总长累加，同时标记这些元素已访问过。

当然，需要直到这些数字是否在我们的数字集内，就需要先将他们存到一个HashSet，随后就可以O(1)时间取数。

同时，由于还是用了一个HashSet记录已访问过元素，所以每个元素只会被访问一次，总时间复杂度控制在O(N)。

## 3.2 代码 ##

class Solution { 
        // 过滤重复数字
        private Set<Integer> records = new HashSet<>();
        // 记录访问过的元素
        private Set<Integer> visited = new HashSet<>();
    
        public int longestConsecutive(int[] nums) { 
            int result = 0;
            if(nums == null || nums.length == 0){ 
                return result;
            }
    
            // 将数字全部过滤
            for(int i = 0; i < nums.length; i++){ 
                records.add(nums[i]);
            }
    
            // 遍历不重复数字，往小于1和大于1方向分别延伸，记录总长即可
            // 每个元素只访问了一次
            for(int i : records){ 
                if(visited.contains(i)){ 
                    continue;
                }
                int total = 1;
                int prev = i - 1;
                while(records.contains(prev)){ 
                    visited.add(prev--);
                    total++;
                }
                int next = i + 1;
                while(records.contains(next)){ 
                    visited.add(next++);
                    total++;
                }
                result = Math.max(result, total);
            }
            return result;
        }
    }

## 3.3 时间复杂度 ##

![在这里插入图片描述][20200607124505912.png]  
O(N)

*  这次速度大幅提升。

## 3.4 空间复杂度 ##

O(N)

# 4 两趟遍历-一个方向延伸 #

## 4.1 思路 ##

前面代码需要分别往大1和小1两个方向延伸，其实我们完全可以找到没有比他小1的那个元素，只需要往大1大那个方向延伸即可。这样都不需要记录元素是否访问过了。

## 4.2 代码 ##

class Solution { 
        // 过滤重复数字
        private Set<Integer> records = new HashSet<>();
    
        public int longestConsecutive(int[] nums) { 
            int result = 0;
            if(nums == null || nums.length == 0){ 
                return result;
            }
    
            // 将数字全部过滤
            for(int i = 0; i < nums.length; i++){ 
                records.add(nums[i]);
            }
    
            // 遍历不重复数字，当某个数字没有比他小1的数字存在，则开始往大1方向查找
            // 每个元素只访问了一次
            for(int i : records){ 
                int prev = i - 1;
                if(records.contains(prev)){ 
                    continue;
                }
                int total = 1;
               
                int next = i + 1;
                while(records.contains(next++)){ 
                    total++;
                }
                result = Math.max(result, total);
            }
            return result;
        }
    }

## 4.3 时间复杂度 ##

![在这里插入图片描述][20200607130121681.png]

## 4.4 空间复杂度 ##

O(N)

[20200607121523449.png]: https://img-blog.csdnimg.cn/20200607121523449.png
[20200607124505912.png]: https://img-blog.csdnimg.cn/20200607124505912.png
[20200607130121681.png]: https://img-blog.csdnimg.cn/20200607130121681.png