【算法】【矩阵和数组模块】数组中的最长连续序列长度

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定数组arr, 求arr中连续序列（不是子数组）的最长长度。
如：
[100, 4, 200, 1, 3, 2]
最长序列为1234， 长度为4

解决方案

原问题：
使用map记录每一个值是否出现，然后计算最长连续的key值即可。

代码编写

java语言版本

原问题：
map版本：

    /**
     * 二轮测试：map法
     * @param arr
     * @return
     */
    public static int maxSeqLenCp1(int[] arr) {
        if(arr == null || arr.length == 0){
            return 0;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        int max = 1;
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {
                // 已经出现过的就不计算了
                continue;
            }
            // 先将当前值放入
            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;
    }

    /**
     * 合并map，只更新边界值为最大值，因为中间值不会拿出来再判断了
     * @param map
     * @param pre
     * @param next
     * @return
     */
    private static int merge(HashMap<Integer, Integer> map, int pre, int next) {
        int left = pre - map.get(pre) + 1;
        int right = map.get(next) + next - 1;
        int len = right - left + 1;
        // 更新边界值
        map.put(left, len);
        map.put(right, len);
        return len;
    }

    public static void main(String[] args) {
        System.out.println(maxSeqLenCp1(new int[]{100, 4, 200, 1,3,2}));
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题其实刚开始我想用类似计数排序的方式申请一个boolean类型的数组，true代表出现过，false代表没有出现过，然后遍历找出最长的连续数组，结果是可以的，但是如果数之间的跨度比较大就会浪费很多空间，所以书上的方式使用了map的方式，map的方法其实存储的数据并不是连续的，但是map可以快速的找到新值的相邻值是否存在，第二个就是只需要将最新的长度更新到数组的两个边界就可以，为什么呢？因为如果数组连续，那么边界中间的值再判断的时候就会continue，只有没有出现过的值才会进行合并操作，而合并操作判断的都是边界值。很巧妙.
总结一下，有时候没有思路的时候可以想一下map是否能够帮得上忙，说不定灵机一动就有方法了。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！