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

128. 最长连续序列

作者: 邦_ | 来源:发表于2022-08-03 15:47 被阅读0次

过是过了。。感觉时间复杂度上还是不太对= =。。
因为排序已经用了o(n)级别的复杂度。再次遍历一遍 又是o(n)复杂度。所以2n。还是o(n)级别?


func longestConsecutive(_ nums: [Int]) -> Int {
        let len = nums.count
        if len == 0 {
            return 0
        }
        let sortNums = nums.sorted()
        var ans = 1
        var temp = 1
        for i in 1..<len {
            let v1 = sortNums[i]
            let v2 = sortNums[i - 1]
            if v1 == v2  {
                continue
            }
            if v1 - v2 == 1 {
                temp += 1
                ans = max(ans,temp)
            }else{
                temp = 1
            }
        }
        return ans
    
    }

}

并查集。。 感觉有点牵强。。要用字典去重。。
但是这个只是用字典就能解决的= =。

class Solution {
class MyUnionFindSize {

    var parents = [Int]()
    var sizes = [Int]()
    init(_ capacity:Int){
        sizes = Array.init(repeating: 1, count: capacity)
        for i in 0..<capacity{
            parents.append(i)
        }
    }
    
    func find(_ v:Int)-> Int {
        
        //路径减半
        var temp = v
        while temp != parents[temp] {
            parents[temp] = parents[parents[temp]]
            temp = parents[temp]
        }
        return temp
        
    }
    func union(_ v1:Int,_ v2:Int) {
        let p1 = find(v1)
        let p2 = find(v2)
        if p1 == p2 {
            return
        }
        let s1 = sizes[p1]
        let s2 = sizes[p2]
        if s1 < s2 {
            parents[p1] = p2
            sizes[p2] += sizes[p1]
        }else {
            parents[p2] = p1
            sizes[p1] += sizes[p2]
        }

        
    } 
}


func longestConsecutive(_ nums: [Int]) -> Int {
        let len = nums.count
        if len == 0 {
            return 0
        }
        var map = [Int:Int]()
        //初始化并查集
        let uf = MyUnionFindSize(len)
        for i in 0..<len {
            let num = nums[i]
            if let _ = map[num] {
                continue
            }
             if let temp = map[num + 1] {
                uf.union(i, temp);
            }
             if let temp = map[num - 1] {
                uf.union(i, temp);
            }
            map[num] = i

        }
        return uf.sizes.max()!
    
    }

}


字典的方法


func longestConsecutive(_ nums: [Int]) -> Int {
        let len = nums.count
        if len == 0 {
            return 0
        }
        var map = [Int:Int]()
        var ans = 1
        for num in nums {
            map[num] = 1
        }
        for num in nums {
            
            if let _ = map[num - 1] {
                continue
            }
            var tempNum = num
            var tempLen = 1
            while map[tempNum + 1] == 1 {
                tempNum += 1
                tempLen += 1
            }
            ans = max(ans, tempLen)
        }
        return ans
    }









相关文章

  • LeetCode-128-最长连续序列

    LeetCode-128-最长连续序列 128. 最长连续序列[https://leetcode-cn.com/p...

  • Leetcode并查集

    128. 最长连续序列[https://leetcode-cn.com/problems/longest-cons...

  • LeetCode 128. 最长连续序列 | Python

    128. 最长连续序列 题目 给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)...

  • 128. 最长连续序列

    128. 最长连续序列 给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示...

  • 128. 最长连续序列

    原题 https://leetcode-cn.com/problems/longest-consecutive-s...

  • 128. 最长连续序列

    https://leetcode-cn.com/problems/longest-consecutive-sequ...

  • 128. 最长连续序列

    解题思路 排序+去重 那么这个题目的时间复杂度是O(N^2) 首先去重, 这里使用unordered_set<> ...

  • 128. 最长连续序列

    题目描述 给定一个未排序的整数数组,找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。 解题思路 直接能想...

  • 128. 最长连续序列

    给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示例: 输入: [100,...

  • 128. 最长连续序列

    题目: 思路: 1.先用set去一次重 2.遍历Set的时候判断一下当前数字是否是Set里连续数字的最小数 3.我...

网友评论

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

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