128. 最长连续序列

过是过了。。感觉时间复杂度上还是不太对= =。。
因为排序已经用了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
    }