美文网首页
leetcode--128--最长连续序列

leetcode--128--最长连续序列

作者: minningl | 来源:发表于2021-06-21 23:58 被阅读0次

    题目:
    给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

    进阶:你可以设计并实现时间复杂度为 O(n) 的解决方案吗?

    示例 1:

    输入:nums = [100,4,200,1,3,2]
    输出:4
    解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
    示例 2:

    输入:nums = [0,3,7,2,5,8,4,6,0,1]
    输出:9

    提示:

    0 <= nums.length <= 104
    -109 <= nums[i] <= 109

    链接:https://leetcode-cn.com/problems/longest-consecutive-sequence

    Python代码:

    class Solution(object):
        def longestConsecutive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums:
                return 0
            size = len(nums)
            
            for i in range(size-1):
                for j in range(size-i-1):
                    if nums[j]>nums[j+1]:
                        nums[j], nums[j+1] = nums[j+1], nums[j]
    
            ret = 1
            ans = 1
            for i in range(size-1):
                if (nums[i+1] == nums[i]+1):
                    ans += 1
                elif (nums[i+1] == nums[i]):
                    continue
                else:
                    ans = 1
                ret = max(ret, ans)
            return ret
    

    Python代码2:

    class Solution(object):
        def longestConsecutive(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums:
                return 0
    
            ret = 0
            dt = {}
    
            for num in nums:
                if num in dt:
                    continue
                left = dt.get(num-1, 0)
                right = dt.get(num+1, 0)
    
                curr = 1+left+right
                dt[num] = curr
                dt[num-left] = curr
                dt[num+right] = curr
                ret = max(ret, curr)
            return ret
    

    Java代码:

    class Solution {
        public int longestConsecutive(int[] nums) {
            Map<Integer, Integer> dt = new HashMap<>();
            if(nums.length==0){
                return 0;
            }
            int ret = 0;
            for(int num:nums){
                if(dt.containsKey(num)){
                    continue;
                }
                int left = dt.getOrDefault(num-1, 0);
                int right = dt.getOrDefault(num+1, 0);
                int curr = 1 + left + right;
                dt.put(num, curr);
                dt.put(num-left, curr);
                dt.put(num+right, curr);
                ret = Math.max(ret, curr);
            }
            return ret;
        }
    }
    

    相关文章

      网友评论

          本文标题:leetcode--128--最长连续序列

          本文链接:https://www.haomeiwen.com/subject/fgksyltx.html