[Swift]LeetCode128. 最长连续序列 | Longest Consecutive Sequence

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

Your algorithm should run in O(n) complexity.

Example:

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.

---

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

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

---

16ms

class Solution {
    func longestConsecutive(_ nums: [Int]) -> Int {
        guard nums.count > 0 else { return 0 }
        var nums = nums.sorted(){$0 < $1}
        
        var longestStreak = 1
        var currentStreak = 1
        for i in 1..<nums.count {
            if nums[i] != nums[i - 1] {
                if nums[i - 1] + 1 == nums[i] {
                    currentStreak += 1
                }else {
                    longestStreak = max(longestStreak, currentStreak) 
                    currentStreak = 1
                }
            }
        }
        return max(longestStreak, currentStreak)
    }
}

---

20ms

class Solution {
    func longestConsecutive(_ nums: [Int]) -> Int {
        let set = Set(nums)
        
        var longestStreak = 0
        
        for s in set {
            if !set.contains(s - 1) {
                var currentNumber = s
                var currentStreak = 1
                
                while set.contains(currentNumber + 1) {
                    currentNumber += 1
                    currentStreak += 1
                }
                
                longestStreak = max(longestStreak, currentStreak)
            }
        }
        
        return longestStreak
    }
}

---

24ms

class Solution {
    func longestConsecutive(_ nums: [Int]) -> Int {
        var numSet = Set(nums)
        var longest = 0
        for num in nums {
            if numSet.contains(num) {
                var left = num - 1
                var right = num + 1
                numSet.remove(num)
                while numSet.contains(left) {
                    numSet.remove(left)
                    left -= 1
                }
                while numSet.contains(right) {
                    numSet.remove(right)
                    right += 1
                }
                longest = max(longest, right - left - 1)
            }
        }
        return longest
    }
}

---

36ms

class Solution {
    func longestConsecutive(_ nums: [Int]) -> Int {
        var set = Set(nums), longest = 0
        
        for num in nums {
            if set.contains(num) {
                set.remove(num)
                let distance = 1 + findConsecutive(&set, num, 1) + findConsecutive(&set, num, -1)
                longest = max(longest, distance)
            }
        }
        
        return longest
    }
    
    fileprivate func findConsecutive(_ set: inout Set<Int>, _ num: Int, _ step: Int) -> Int {
        var len = 0, num = num + step
    
        while set.contains(num) {
            set.remove(num)
            len += 1
            num += step
        }
        
        return len
    }
}

---

 48ms

class Solution {
    func longestConsecutive(_ nums: [Int]) -> Int {
        guard nums.count > 1 else {
            return nums.count
        }

        let sorted = nums.sorted()
        var last = 0
        var maxLength = 1
        var duplicated = 0

        for idx in 1 ..< sorted.count {
            if sorted[idx] == sorted[idx - 1] {
                duplicated += 1
            } else if sorted[idx] == sorted[idx - 1] + 1 {
                let length = idx - duplicated - last + 1
                maxLength = max(maxLength, length)
            } else {
                duplicated = 0
                last = idx
            }
        }

        return maxLength
    }
}

---

56ms

public struct HashSet<T: Hashable> {
  private var dictionary = Dictionary<T, Bool>()
    
  public mutating func insert(element: T) {
    dictionary[element] = true
  }
  public mutating func remove(element: T) {
    dictionary[element] = nil
  }
  public func contains(element: T) -> Bool {
    return dictionary[element] != nil
  }
  public func allElements() -> [T] {
    return Array(dictionary.keys)
  }
  public var count: Int {
    return dictionary.count
  }
  public var isEmpty: Bool {
    return dictionary.isEmpty
  }
}

/*
 * Copyright (c) 2018 Brad McEvilly
 */
class Solution {
    func longestConsecutive(_ nums: [Int]) -> Int {
        
        var maxStreak:Int=0
        var numSet = HashSet<Int>()
        
        // validate input
        if (0 == nums.count || nums==nil){
            //print("validation for nums - nums:\(nums)")
            return maxStreak
        }
        
        for i in (0..<nums.count) {
            //print("num at index \(i): \(nums[i])")
            numSet.insert(element:nums[i])
        }
        for numKey in numSet.allElements() {
            //print("numKey: \(numKey)")
            var preVal = numKey-1
            //print("preVal: \(preVal)")
            if(!numSet.contains(element:preVal)){
                //print("if numSet contains element preVal")
                var curNum = numKey
                var curStreak = 1
                while numSet.contains(element:(curNum+1)){
                    curNum+=1
                    curStreak+=1
                }
                maxStreak = max(maxStreak, curStreak)
            }
        }
        return maxStreak
    }
}