[Swift]LeetCode164.最大间距|MaximumGap

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

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

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

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

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

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

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Return 0 if the array contains less than 2 elements.

Example 1:

Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
             (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Note:

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
Try to solve it in linear time/space.

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

示例 1:

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例 2:

输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。

说明:

你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

48ms

 1 class Solution {
 2     func maximumGap(_ nums: [Int]) -> Int {
 3 if nums.count < 2 {
 4         return 0
 5     }
 6     var minNums = INTPTR_MAX
 7     var maxNums = 0
 8     for i in nums {
 9         if i < minNums {
10             minNums = i
11         }
12         if i > maxNums {
13             maxNums = i
14         }
15     }
16     let gap = max(1,(maxNums - minNums) / (nums.count - 1))
17     let bucketNum = (maxNums - minNums) / gap + 1
18     var bucketMax = [Int](repeating: 0, count: bucketNum)
19     var bucketMin = [Int](repeating: INTPTR_MAX, count: bucketNum)
20     var bucketUsed = [Bool](repeating: false, count: bucketNum)
21     for i in nums {
22         let n = (i - minNums) / gap
23         bucketUsed[n] = true
24         if i > bucketMax[n] {
25             bucketMax[n] = i
26         }
27         if i < bucketMin[n] {
28             bucketMin[n] = i
29         }
30     }
31     var maxGap = 0
32     var previousMax = minNums
33     for n in (0..<bucketNum) {
34         if bucketUsed[n] {
35             maxGap = max(maxGap, bucketMin[n] - previousMax)
36             previousMax = bucketMax[n]
37         }
38     }
39     return maxGap
40     }
41 }

52ms

 1 class Solution {
 2     func maximumGap(_ nums: [Int]) -> Int {
 3         var maxGap = 0
 4         if nums.count < 2 { return maxGap }
 5         
 6         var start = 0
 7         let sortedArray = nums.sorted()
 8         while (start < sortedArray.count - 1) {
 9             let diff = sortedArray[start + 1] - sortedArray[start]
10             maxGap = max(diff, maxGap)
11             start += 1
12         }
13         
14         return maxGap
15     }
16 }

56ms

 1 class Solution {
 2     func maximumGap(_ nums: [Int]) -> Int {
 3         if nums.isEmpty || nums.count == 1 {return 0}
 4         var nums: [Int] = nums.sorted(by:<)
 5         var ret:Int = 0
 6         for i in 1..<nums.count
 7         {
 8             ret = max(ret, nums[i]-nums[i-1])
 9         }
10         return ret
11     }
12 }

56ms

 1 class Solution {
 2     func maximumGap(_ nums: [Int]) -> Int {
 3         if nums.count < 2 {
 4             return 0
 5         }
 6         var res = 0
 7         var maxn = 0
 8         var minn = Int.max
 9         for i in 0..<nums.count {
10             maxn = max(maxn, nums[i])
11             minn = min(minn, nums[i])
12         }
13         
14         let n = (maxn - minn) / nums.count + 1
15         let buckets = (maxn - minn) / n + 1
16         var maxs = Array(repeating: minn-1, count: buckets)
17         var mins = Array(repeating: maxn+1, count: buckets)
18         for i in 0..<nums.count {
19             let index = (nums[i] - minn) / n
20             mins[index] = min(mins[index], nums[i])
21             maxs[index] = max(maxs[index], nums[i])
22         }
23         
24         var i = 0
25         while i < buckets  {
26             while maxs[i] == minn - 1 {
27                 i+=1
28             }
29             var j = i+1
30             if j>=buckets {
31                 break
32             }
33             while mins[j] == maxn + 1 {
34                 j += 1
35             }
36             res = max(res,mins[j] - maxs[i])
37             
38             i = j
39         }
40         
41         return res
42     }
43 }