[Swift]LeetCode128.最长连续序列|LongestConsecutiveSequence

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

 1 class Solution {
 2     func longestConsecutive(_ nums: [Int]) -> Int {
 3         guard nums.count > 0 else { return 0 }
 4         var nums = nums.sorted(){$0 < $1}
 5         
 6         var longestStreak = 1
 7         var currentStreak = 1
 8         for i in 1..<nums.count {
 9             if nums[i] != nums[i - 1] {
10                 if nums[i - 1] + 1 == nums[i] {
11                     currentStreak += 1
12                 }else {
13                     longestStreak = max(longestStreak, currentStreak) 
14                     currentStreak = 1
15                 }
16             }
17         }
18         return max(longestStreak, currentStreak)
19     }
20 }

20ms

 1 class Solution {
 2     func longestConsecutive(_ nums: [Int]) -> Int {
 3         let set = Set(nums)
 4         
 5         var longestStreak = 0
 6         
 7         for s in set {
 8             if !set.contains(s - 1) {
 9                 var currentNumber = s
10                 var currentStreak = 1
11                 
12                 while set.contains(currentNumber + 1) {
13                     currentNumber += 1
14                     currentStreak += 1
15                 }
16                 
17                 longestStreak = max(longestStreak, currentStreak)
18             }
19         }
20         
21         return longestStreak
22     }
23 }

24ms

 1 class Solution {
 2     func longestConsecutive(_ nums: [Int]) -> Int {
 3         var numSet = Set(nums)
 4         var longest = 0
 5         for num in nums {
 6             if numSet.contains(num) {
 7                 var left = num - 1
 8                 var right = num + 1
 9                 numSet.remove(num)
10                 while numSet.contains(left) {
11                     numSet.remove(left)
12                     left -= 1
13                 }
14                 while numSet.contains(right) {
15                     numSet.remove(right)
16                     right += 1
17                 }
18                 longest = max(longest, right - left - 1)
19             }
20         }
21         return longest
22     }
23 }

36ms

 1 class Solution {
 2     func longestConsecutive(_ nums: [Int]) -> Int {
 3         var set = Set(nums), longest = 0
 4         
 5         for num in nums {
 6             if set.contains(num) {
 7                 set.remove(num)
 8                 let distance = 1 + findConsecutive(&set, num, 1) + findConsecutive(&set, num, -1)
 9                 longest = max(longest, distance)
10             }
11         }
12         
13         return longest
14     }
15     
16     fileprivate func findConsecutive(_ set: inout Set<Int>, _ num: Int, _ step: Int) -> Int {
17         var len = 0, num = num + step
18     
19         while set.contains(num) {
20             set.remove(num)
21             len += 1
22             num += step
23         }
24         
25         return len
26     }
27 }

48ms

 1 class Solution {
 2     func longestConsecutive(_ nums: [Int]) -> Int {
 3         guard nums.count > 1 else {
 4             return nums.count
 5         }
 6 
 7         let sorted = nums.sorted()
 8         var last = 0
 9         var maxLength = 1
10         var duplicated = 0
11 
12         for idx in 1 ..< sorted.count {
13             if sorted[idx] == sorted[idx - 1] {
14                 duplicated += 1
15             } else if sorted[idx] == sorted[idx - 1] + 1 {
16                 let length = idx - duplicated - last + 1
17                 maxLength = max(maxLength, length)
18             } else {
19                 duplicated = 0
20                 last = idx
21             }
22         }
23 
24         return maxLength
25     }
26 }

56ms

 1 public struct HashSet<T: Hashable> {
 2   private var dictionary = Dictionary<T, Bool>()
 3     
 4   public mutating func insert(element: T) {
 5     dictionary[element] = true
 6   }
 7   public mutating func remove(element: T) {
 8     dictionary[element] = nil
 9   }
10   public func contains(element: T) -> Bool {
11     return dictionary[element] != nil
12   }
13   public func allElements() -> [T] {
14     return Array(dictionary.keys)
15   }
16   public var count: Int {
17     return dictionary.count
18   }
19   public var isEmpty: Bool {
20     return dictionary.isEmpty
21   }
22 }
23 
24 /*
25  * Copyright (c) 2018 Brad McEvilly
26  */
27 class Solution {
28     func longestConsecutive(_ nums: [Int]) -> Int {
29         
30         var maxStreak:Int=0
31         var numSet = HashSet<Int>()
32         
33         // validate input
34         if (0 == nums.count || nums==nil){
35             //print("validation for nums - nums:\(nums)")
36             return maxStreak
37         }
38         
39         for i in (0..<nums.count) {
40             //print("num at index \(i): \(nums[i])")
41             numSet.insert(element:nums[i])
42         }
43         for numKey in numSet.allElements() {
44             //print("numKey: \(numKey)")
45             var preVal = numKey-1
46             //print("preVal: \(preVal)")
47             if(!numSet.contains(element:preVal)){
48                 //print("if numSet contains element preVal")
49                 var curNum = numKey
50                 var curStreak = 1
51                 while numSet.contains(element:(curNum+1)){
52                     curNum+=1
53                     curStreak+=1
54                 }
55                 maxStreak = max(maxStreak, curStreak)
56             }
57         }
58         return maxStreak
59     }
60 }