• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode164.最大间距|MaximumGap

原作者: [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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode477.汉明距离总和|TotalHammingDistance发布时间:2022-07-14
下一篇:
在Xcode中加载并使用TensorFlow For Swift发布时间:2022-07-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap