leetcode - [128] Longest Consecutive Sequence

2020/04/19

题目描述

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

给你一个无序数组,计算其中最长连续序列的长度。

举个例子:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Update at 2020_0725

记得跳过重复元素,如: nums = [1, 2, 0, 1]

if (map.containsKey(i)) continue;

Update at 2020_0627

重新来看下这张图。

当我再次做这道题的时候,我就一直在思考一个问题: 拼接左右时,如何调整最左和最右的值?

比如,上图中的最后一步,若当前元素为4,如何将16对于的value调整为6

换句话说,如何定位到key = 1key = 6

先看左边,key = 3,它对应的value = 3,说明什么?

截止至3,它的最长连续序列的长度为3

还有一层意思,在它之前(包括它),共有三个元素!

所以: 4 - 3 = 1,你找到了最左边,你想修改的key

右边同理。

if (l > 0) map.put(cur - l, sum);
if (r > 0) map.put(cur + r, sum);

解法1

Thanks @dchen0215 and @wangliang

MapkeySet中已存在n,直接跳过。

然后,分别计算左右两边元素的值,默认为零。

当前元素的值等于左右相加,再算上自己,也就是加1,并将其存入Map中。

接着,更新最大值。

最后,若有需要,调整左右边界。

class Solution {
    public int longestConsecutive(int[] nums) {
        HashMap<Integer, Integer> hMap = new HashMap<>(64);
        int max = 0;
        for (int n: nums){
            if (hMap.containsKey(n)){
                continue;
            }
            int l = hMap.getOrDefault(n - 1, 0);
            int r = hMap.getOrDefault(n + 1, 0);
            int sum = l + r + 1;
            max = Math.max(max, sum);
            hMap.put(n, sum);
            if (l > 0) hMap.put(n - l, sum);
            if (r > 0) hMap.put(n + r, sum);
        }
        return max;
    }
}

Enjoy it!

解法2 - Update 2020_0524

过了一个月,上面那种解法完全想不起来。

发现一种更容易的解法:

Thanks @jeantimex

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int n: nums){
            set.add(n);
        }

        int max = 0;
        for (int i = 0; i < nums.length; i++){
            int count = 1;

            int cur = nums[i];
            // Left
            while (set.contains(--cur)){
                count++;
                set.remove(cur);
            }

            // Right
            cur = nums[i];
            while (set.contains(++cur)){
                count++;
                set.remove(cur);
            }

            max = Math.max(max, count);
        }
        return max;
    }
}

Enjoy it!


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory