128. Longest Consecutive Sequence(hard)
in leetcode with 0 comment

128. Longest Consecutive Sequence(hard)

in leetcode with 0 comment

[toc]

128. Longest Consecutive Sequence(hard)

原题链接 128. Longest Consecutive Sequence

题意

image-20200406161614905

解题思路

审题可得题意是想求得数组中最长的连续序列的长度,但是数组并不是有序数组。如果是有序数组这题完全可以用动态规划来解。

排序+动态规划

1、我们可以使用排序+动态规划 来解 时间复杂度是O(nlogn) 不符合题目要求

代码就不贴了 这只是思路的一种

归并集

2、我们可以使用 归并集来解

遍历原数组 判断uf[i] 与 uf[i+1]的起始值是不是同一个

AC代码

Map<Integer, Integer> um = new HashMap<>();
    Map<Integer, Integer> cnt = new HashMap<>();

    /**
     * 归并集解法
     */
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        for (int num : nums) {
            um.put(num, num);
            cnt.put(num, 1);
        }
        int ans = 1;
        for (int i : nums) {
            if (i != Integer.MAX_VALUE && um.containsKey(i + 1)) {
                ans = Math.max(ans, merge(i, i + 1));
            }
        }
        return ans;
    }

    private int find(int i) {
        if (i == um.get(i)) {
            return i;
        }
        // 压缩路径
        int res = find(um.get(um.get(i)));
        um.put(i, res);
        return res;
    }

    private int merge(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px == py) {
            return cnt.get(px);
        }
        um.put(y, px);
        cnt.put(px, cnt.get(px) + cnt.get(py));
        return cnt.get(px);
    }

HashSet

这题还可以使用Set的特性来解决,这些数字用一个 HashSet 保存,实现 O(1) 时间的查询,同时,我们只对 当前数字 - 1 不在哈希表里的数字,作为连续序列的第一个数字去找对应的最长序列,这是因为其他数字一定已经出现在了某个序列里。

AC代码

 public int longestConsecutive1(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int ans = 0;
        for(int i: set){
            // 假如一个数在哈希表中存在比他小的,那么它不是可以作为开头的数字
            if(i != Integer.MIN_VALUE && set.contains(i-1)){
                continue;
            }
            int cnt = 1;
            while(i!=Integer.MAX_VALUE && set.contains(i+1)){
                cnt ++;
                i++;
            }
            ans = Math.max(ans, cnt);
        }
        return ans;

    }