[题目]
给定无序数组 arr, 返回其中最长的连续序列的长度.
[举例]
arr=[100,4,200,1,3,2], 最长的连续序列为 [1,2,3,4], 所以返回 4.
[难度]
二星
[解答]
本题利用哈希表可以实现时间复杂度为 O(N), 额外空间复杂度为 O(N) 的方法. 具体实现方法如下:
1. 生成哈希表 HashMap<Integer, Integer> map,key 代表遍历过的某个数, value 代表 key 这个数所在的最长连续序列的长度. 同时 map 还可以表示 arr 中的一个数之前是否出现过.
2. 从左到右遍历 arr, 假设遍历到 arr[i]. 如果 arr[i] 之前出现过, 直接遍历下一个数, 只处理之前没出现过的 arr[i]. 首先在 map 中加入记录 (arr[i], 1), 代表目前 arr[i] 单独作为一个连续序列. 然后看 map 中是否含有 arr[i] - 1, 如果有, 则说明 arr[i] - 1 所在的连续序列可以和 arr[i] 合并, 合并后记为 A 序列. 利用 map 可以得到 A 序列的长度, 记为 lenA, 最小值记为 leftA, 最大值记为 rightA, 只在 map 中更新与 leftA 和 rightA 有关的记录, 更新成 (leftA, lenA) 和 (rightA, lenA). 接下来看 map 中是否含有 arr[i] + 1, 如果有, 则说明 arr[i] + 1 所在的连续序列可以与 A 合并, 合并后记为 B 序列. 利用 map 可以得到 B 序列的长度为 lenB, 最小值记为 leftB, 最大值记为 rightB, 只在 map 中更新与 leftB 和 rightB 有关的记录, 更新成 (leftB, lenB) 和 (rightB, lenB).
3. 遍历的过程中用全局变量 max 记录每次合并出的序列的长度最大值, 最后返回 max.
整个过程中, 只是每个连续序列最小值和最大值在 map 中的记录有意义, 中间数的记录不再更新, 因为再也不会使用到. 这是因为我们只处理之前没有出现的数, 如果一个出现的数能够把某个连续区间扩大, 或把某两个连续区间连在一起, 毫无疑问, 只需要 map 中有关这个连续区间最小值和最大值的记录.
具体过程请参看如下代码中的 longestConsecutive 方法:
- import java.util.HashMap;
- public class Main {
- public static void main(String[] args) {
- int[] arr = {100,4,200,1,3,2};
- System.out.println(new Main().longestConsecutive(arr));//4
- }
- public int longestConsecutive(int[] arr){
- if(arr == null || arr.length == 0) return 0;
- int max = 1;
- HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
- for(int i = 0, len = arr.length; i <len; i++){
- if(!map.containsKey(arr[i])){
- map.put(arr[i], 1);
- if(map.containsKey(arr[i] - 1)){
- max = Math.max(max, merge(map, arr[i] - 1, arr[i]));
- }
- if(map.containsKey(arr[i]+1)){
- max = Math.max(max, merge(map, arr[i], arr[i] + 1));
- }
- }
- }
- return max;
- }
- public int merge(HashMap<Integer, Integer> map, int Less, int more){
- int left = Less - map.get(Less) + 1;
- int right = more + map.get(more) - 1;
- int len = right - left + 1;
- map.put(left, len);
- map.put(right, len);
- return len;
- }
- }
来源: http://www.bubuko.com/infodetail-2995692.html