[Swift]LeetCode414.第三大的数|ThirdMaximumNumber

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

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

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

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

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

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

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

示例 1:

输入: [3, 2, 1]

输出: 1

解释: 第三大的数是 1.

示例 2:

输入: [1, 2]

输出: 2

解释: 第三大的数不存在, 所以返回最大的数 2 .

示例 3:

输入: [2, 2, 3, 1]

输出: 1

解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
存在两个值为2的数，它们都排第二。

12ms:用元组记录数值

 1 class Solution {
 2     func thirdMax(_ nums: [Int]) -> Int {
 3         var (num0,num1,num2) = (Int.min,Int.min,Int.min)
 4         for num in nums {
 5             if num == num0 || num == num1 || num == num2 {
 6                 continue
 7             }
 8             if num > num0 {
 9                 (num0,num1,num2) = (num,num0,num1)
10                 continue
11             }
12             if num > num1 {
13                 (num1,num2) = (num,num1)
14                 continue
15             }
16             if num > num2 {
17                 num2 = num
18             }
19         }
20         return num2 == Int.min ? num0 : num2
21     }
22 }

16ms

 1 class Solution {
 2     func thirdMax(_ nums: [Int]) -> Int {
 3         var firstMax = nums[0]
 4         var secondMax: Int?
 5         var thirdMax: Int?
 6         
 7         // get max
 8         for num in nums {
 9             firstMax = max(firstMax, num)
10         }
11         // get 2nd max
12         for num in nums {
13             if num < firstMax {
14                 if let curSecondMax = secondMax {
15                     secondMax = max(curSecondMax, num)
16                 } else {
17                     secondMax = num
18                 }
19             }
20         }
21         
22         if secondMax == nil {
23             return firstMax
24         }
25         
26         for num in nums {
27             if num < secondMax! {
28                 if let curThirdMax = thirdMax {
29                     thirdMax = max(curThirdMax, num)
30                 } else {
31                     thirdMax = num
32                 }
33             }
34         }
35         
36         return thirdMax ?? firstMax
37     }
38 }

16ms

 1 class Solution {
 2     func thirdMax(_ nums: [Int]) -> Int {
 3         var firstMax = Int.min
 4         var secondMax = Int.min
 5         var thirdMax = Int.min
 6         var count = 0
 7 
 8         for num in nums {
 9             if num > firstMax {
10                 (thirdMax, secondMax, firstMax) = (secondMax, firstMax, num)
11                 count += 1
12             } else if num != firstMax && num > secondMax {
13                 (thirdMax, secondMax) = (secondMax, num)
14                 count += 1
15             } else if num != firstMax && num != secondMax && num > thirdMax {
16                 thirdMax = num
17                 count += 1
18             }
19         }
20 
21         if count < 3 {
22             return firstMax
23         }
24 
25         return thirdMax
26     }
27 }

20ms

 1 class Solution {
 2     func thirdMax(_ nums: [Int]) -> Int {
 3         var max = nums[0]
 4         var second: Int?
 5         var third: Int?
 6         
 7         for i in 1..<nums.count {
 8             if nums[i] < max {
 9                 if second == nil {
10                     second = nums[i]
11                 } else {
12                     if second! < nums[i] {
13                         third = second!
14                         second = nums[i]
15                     } else if second! > nums[i] {
16                         if third == nil {
17                             third = nums[i]
18                         } else {
19                             if nums[i] > third! {
20                                 third = nums[i]
21                             }
22                         }
23                         
24                     }
25                 }
26                 
27             } else if nums[i] > max {
28                 third = second
29                 second = max
30                 max = nums[i]
31             }
32         }
33         
34         if third != nil {
35             return third!
36         }
37         
38         return max
39     }
40 }

24ms

 1 class Solution {
 2     func thirdMax(_ nums: [Int]) -> Int {
 3         var setNum = Set<Int>(nums)
 4         var queue = Queue<Int>(size: 3)
 5         
 6         for num in setNum {
 7             if queue.count < 3 {
 8                 queue.push(value: num)
 9             } else if let min = queue.min() {
10                 if num > min {
11                     queue.pop()
12                     queue.push(value: num)
13                 }
14             } else {
15                 queue.push(value: num)
16             }
17         }
18         
19         if queue.count < 3 {
20             while queue.count != 1 {
21                 queue.pop()
22             }
23         }
24 
25         return queue.min() ?? 0       
26     }    
27 }
28 
29 class Queue<T: Comparable> {
30     private var data = [T]()
31     private let size: Int
32     var count: Int {
33         return data.count
34     }
35     init(size: Int) {
36         self.size = size
37     }
38     
39     func push(value: T) {
40         if data.isEmpty {
41             data.append(value)
42         } else if data.count + 1 > size {
43             if let last = data.first {
44                 if value < last {
45                     data.removeFirst()
46                     push(value: value)
47                 }
48             }
49         } else {
50             var toInsertAt = -1
51             for (index, dataValue) in data.enumerated() {
52                 if value > dataValue {
53                     toInsertAt = index
54                     break
55                 }
56             }
57             if toInsertAt == -1 {
58                 data.append(value)
59             } else {
60                 data.insert(value, at: toInsertAt)
61             }
62         }
63     }
64     
65     @discardableResult
66     func pop() -> T? {
67         return data.popLast()
68     }
69     
70     @discardableResult
71     func min() -> T? {
72         if data.isEmpty {
73             return nil
74         } else {
75             return data.last
76         }
77     }   
78 }