Fork me on GitHub

Maximum Gap

题目介绍

LeetCode 164. Maximum Gap,题目的意思给定一个未排序的数组,找到在排序情况下相邻两个数最大差值。要在线性时间和空间内解决,< 2 个元素返回 0。

解题思路

首先想到的是利用系统的 sort() 进行排序,但是明显超时。最大的差值肯定大于 (maxValue - minValue) / (nums.count - 1),很容易想到桶排序(当然我没想到,看了 Discuss 之后才想到)。那么令桶空间为 (maxValue - minValue) / (nums.count - 1)。排序完成后,只需要依次将相邻桶空间,后空间最小值减去前空间的最大值,然后寻找其中的最大值。

PS:

  1. 桶空间 max(1, (maxValue - minValue) / (nums.count - 1)),处理最大值和最小相等、差值比个数小太多的情况。
  2. 桶个数 (maxValue - minValue) / bucketCount + 1,极限值[1, 10000000]。
  3. preBucketMax 记录前空间的最大值,因为有可能后一个桶空间为空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
struct Bucket {
public var empty: Bool = true
public var maxValue: Int = Int.min
public var minValue: Int = Int.max
}
func maximumGap(_ nums: [Int]) -> Int {
if nums.isEmpty || nums.count < 2 {
return 0
}
let maxValue = nums.max()!, minValue = nums.min()!
let bucketCount = max(1, (maxValue - minValue) / (nums.count - 1))//处理最大值和最小相等、差值比个数小太多的情况
let bucketNum = (maxValue - minValue) / bucketCount + 1//极限值[1, 10000000]
var buckets = Array(repeatElement(Bucket(), count: bucketNum))
for num in nums {
let index = (num - minValue) / bucketCount
buckets[index].empty = false
buckets[index].maxValue = max(num, buckets[index].maxValue)
buckets[index].minValue = min(num, buckets[index].minValue)
}
var preBucketMax = minValue, maxGap: Int = 0
for bucket in buckets {
if bucket.empty {
continue
}
maxGap = max(bucket.minValue - preBucketMax, maxGap)
preBucketMax = bucket.maxValue
}
return maxGap
}
}

版权声明



Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于Ivan’s Blog | 叶帆的博客博客( http://yeziahehe.com ),版权所有,侵权必究。

本文链接:http://yeziahehe.com/2017/10/16/MaximumGap/