[Swift]LeetCode220.存在重复元素III|ContainsDuplicateIII

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

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

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

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

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

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

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i]and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = 0
Output: true

Example 2:

Input: nums = 2
Output: true

Example 3:

Input: nums = 3
Output: false

给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。

示例 1:

输入: nums = [1,2,3,1], k= 3, t = 0
输出: true

示例 2:

输入: nums = [1,0,1,1], k=1, t = 2
输出: true

示例 3:

输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false

52ms

 1 class Solution {
 2     func containsNearbyAlmostDuplicate(_ nums: [Int], _ k: Int, _ t: Int) -> Bool {
 3         var set: Set<Int> = []
 4         for (index, num) in nums.enumerated() {
 5             if t == 0 {
 6                 if set.contains(num) {
 7                     return true
 8                 }
 9             } else {
10                 if set.contains(where: { abs($0 - num) <= t }) {
11                     return true
12                 }
13             }
14 
15             set.insert(num)
16 
17             if index >= k {
18                 set.remove(nums[index - k])
19             }
20         }
21 
22         return false
23     }
24 }

60ms

 1 class Solution {
 2     func containsNearbyAlmostDuplicate(_ nums: [Int], _ k: Int, _ t: Int) -> Bool {
 3         if nums.isEmpty || nums.count < 2 {
 4             return false
 5         }
 6         var indices = [Int](0 ..< nums.count)
 7         indices = indices.sorted(by: { a, b in nums[a] < nums[b] } )
 8         
 9         for i in 0 ..< nums.count {
10             var x = indices[i]
11             for j in (i + 1) ..< nums.count {
12                 var y = indices[j]
13                 var diffNums = nums[y] - nums[x]
14                 var diffIndex = abs(x - y)
15                 if diffNums > t {
16                      break
17                 }
18                 if diffIndex <= k {
19                     return true
20                 }
21             }
22         }
23         return false
24     }
25 }

88ms

 1 class Solution {
 2     func containsNearbyAlmostDuplicate(_ nums: [Int], _ k: Int, _ t: Int) -> Bool {
 3         if nums.count <= 1 || k < 1 || t < 0 {
 4             return false
 5         }
 6         
 7         let mins = nums.min()!
 8         var bucktes = [Int : Int]()
 9         for i in 0..<nums.count {
10             if i > k {
11                 let key = (nums[i-k-1] - mins) / (t+1)
12                 bucktes.removeValue(forKey: key)
13             }
14             let key = (nums[i] - mins) / (t + 1)
15             if bucktes.keys.contains(key) {
16                 return true
17             }
18             if let left = bucktes[key-1] , nums[i] - left <= t {
19                 return true
20             }
21             if let right = bucktes[key+1], right - nums[i] <= t {
22                 return true
23             }
24             bucktes[key] = nums[i]
25         }
26         
27         return false
28     }
29 }