当前位置:网站首页>最长连续序列[扩散法+空间换时间]

最长连续序列[扩散法+空间换时间]

2022-06-24 21:17:00 REN_林森

前言

空间换时间核心是为了降低时间复杂度,但有时候是解题的关键,毕竟时间有限(先双指针一样)。
典型的空间换时间就是数组/数组hash/hash。
本文通过最长连续序列来感受空间换时间,并练习扩散法。

一、最长连续序列

在这里插入图片描述

二、扩散法+空间换时间

package everyday.medium;

import java.util.HashSet;
import java.util.Set;

// 最长连续序列
public class LongestConsecutive {
    
    /* target:找到里面最长连续数字,如果排个序,直接O(n)遍历一遍记录到最长即可。 但是时间复杂度要求O(n),所以只能空间换时间,先用hash存起来,方便后面快速查找(以扩散法查找)。 */
    public int longestConsecutive(int[] nums) {
    
        // 特殊情况,特殊处理。
        if (0 == nums.length) return 0;
        Set<Integer> set = new HashSet<>();
        // 准备工作,记录所有元素,并赋初值为1,表示连续个数1。
        for (int n : nums) if (!set.contains(n)) set.add(n);
        // 遍历nums,求相邻的元素的总连续度。
        int ans = 1;
        // 扩散法,每个值最多被访问两次,一次有,一次无。
        for (int n : nums) {
    
            // 没有用过的数字,才从两边扩散开来。
            if (set.contains(n)) {
    
                // 开始往两边扩散,扩散法。
                int len = 1;
                int left = n, right = n;
                while (set.contains(--left)) {
    
                    ++len;
                    set.remove(left);
                }
                while (set.contains(++right)) {
    
                    ++len;
                    set.remove(right);
                }
                // 取每次能扩散的最大长度。
                ans = Math.max(ans, len);
            }
        }
        return ans;
    }
}

总结

1)空间换时间
2)扩散法

参考文献

[1] LeetCode 最长连续序列

原网站

版权声明
本文为[REN_林森]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_43164662/article/details/125448794