[Swift]LeetCode532. 数组中的K-diff数对 | K-diff Pairs in an

发布时间：2020-12-14 05:10:56 所属栏目：百科来源：网络整理

导读：Given an array of integers and an integer?k,you need to find the number of?unique?k-diff pairs in the array. Here a?k-diff?pair is defined as an integer pair (i,j),where?i?and?j?are both numbers in the array and their?absolute difference?i

Given an array of integers and an integer?k,you need to find the number of?unique?k-diff pairs in the array. Here a?k-diff?pair is defined as an integer pair (i,j),where?i?and?j?are both numbers in the array and their?absolute difference?is?k.

Example 1:

Input: [3,1,4,5],k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array,(1,3) and (3,5).
Although we have two 1s in the input,we should only return the number of unique pairs.

?Example 2:

Input:[1,2,3,k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array,2),(2,3),(3,4) and (4,5).

?Example 3:

Input: [1,5,4],k = 0
Output: 1
Explanation: There is one 0-diff pair in the array,1).

?Note:

The pairs (i,j) and (j,i) count as the same pair.
The length of the array won‘t exceed 10,000.
All the integers in the given input belong to the range: [-1e7,1e7].


 1 class Solution {
 2     func findPairs(_ nums: [Int],_ k: Int) -> Int {
 3         var count:Int = 0
 4         if k < 0 {return count}
 5         var hm:[Int:Int] = [Int:Int]()
 6         let len:Int = nums.count
 7         for i in 0..<len
 8         {
 9             hm[nums[i]] = i
10         }
11         for i in 0..<len
12         {
13 //如果字典包含所请求键的值，则下标返回包含该键的现有值的可选值。否则，下标返回nil：
14             if let keys = hm[nums[i] + k] 
15             {
16                 if keys != i
17                 {
18                     count += 1
19 //使用下标语法通过nil为该键指定值来从字典中删除键值对
20 //使用该removeValue(forKey:)方法从字典中删除键值对。hm.removeValue(forKey:key)
21 //此方法删除键值对（如果存在）并返回已删除的值，nil如果不存在值则返回
22                     hm[nums[i] + k] = nil                    
23                 }
24             }
25         }
26         return count
27     }
28 }

44ms

 1 class Solution {
 2     func findPairs(_ nums: [Int],_ k: Int) -> Int {
 3         guard k >= 0 else {
 4             return 0
 5         }
 6         
 7         var dict = [Int: Int]()
 8         for num in nums {
 9             //dict[num] = dict[num] == nil ? 0 : dict[num]! + 1
10             dict[num,default: 0] += 1
11         }
12         
13         var res = 0
14         for (num,count) in dict {
15             if k == 0 {
16                 if count > 1 {
17                     res += 1
18                 } 
19             } else {
20                 if dict[num - k] != nil {
21                     res += 1
22                 }
23             }
24             
25         }
26         return res
27     }
28 }

48ma

 1 class Solution {
 2     func findPairs(_ nums: [Int],_ k: Int) -> Int {
 3         guard nums.count > 1 else { return 0 }
 4         guard k >= 0 else { return 0 }
 5 
 6         var res = 0
 7         var dict = [Int: Int]()
 8         for n in nums {
 9             if let val = dict[n] {
10                 dict[n] = val + 1
11             } else {
12                 dict[n] = 1
13             }
14         }
15         
16         if k == 0 {
17             return dict.reduce(0) { (r,arg1) -> Int in
18                 if arg1.value > 1 {  return r + 1}
19                 return r
20             }
21         } else {
22             for key in dict.keys {
23                 if dict.keys.contains(key + k) {
24                     res = res + 1
25                 }
26             }
27             return res
28         }
29     }
30 }

52ms

 1 class Solution {
 2     func findPairs(_ nums: [Int],_ k: Int) -> Int {
 3         guard k >= 0 else {
 4             return 0
 5         }
 6         
 7         var dict = [Int: Int]()
 8         for num in nums {
 9             dict[num,default: 0] += 1
10         }
11         
12         var res = 0
13         for (num,count) in dict {
14             if k == 0 {
15                 if count > 1 {
16                     res += 1
17                 } 
18             } else {
19                 if dict[num - k] != nil {
20                     res += 1
21                 }
22             }
23             
24         }
25         return res
26     }
27 }

56ms

 1 class Solution {
 2     func findPairs(_ nums: [Int],_ k: Int) -> Int {
 3         var dict = [Int: Bool]()
 4         
 5         if k < 0 {
 6             return 0
 7         }
 8         
 9         var diff = k < 0 ? -1*k : k
10         var count = 0
11         
12         
13         
14         for num in nums {
15             if !dict.keys.contains(num) {
16                 dict[num] = false
17                 if diff == 0 { continue }
18             }
19             
20             if dict.keys.contains(num-diff) {
21                 if dict[num-diff] == false {
22                     dict[num-diff] = true
23                     count = count + 1
24                 }
25                 
26             } 
27             if dict.keys.contains(num+diff) {
28                 if dict[num] == false {
29                     dict[num] = true
30                     count = count + 1
31                 }
32             }
33         }
34         
35         return count
36     }
37 }

68ms

 1 class Solution {
 2     func findPairs(_ nums: [Int],_ k: Int) -> Int {
 3         
 4         guard k >= 0 else { return 0 }
 5         
 6         var dict = nums.reduce(into: [Int: Int]()) { dict,num in
 7             dict[num,default:0] += 1
 8         }
 9         
10         guard k > 0 else {
11             return dict.reduce(into: 0) { count,numAndCount in
12                 if numAndCount.1 > 1 {
13                     count += 1
14                 }
15             }
16         }
17         
18         var totalCount = 0
19         for (num,count) in dict {
20             if dict[num+k,default:0] > 0 {
21                 totalCount += 1
22             }
23             if dict[num-k,default: 0] > 0 {
24                 totalCount += 1
25             }
26             dict[num] = 0
27         }
28         
29         return totalCount
30     }
31 }

76ms

 1 class Solution {
 2     func findPairs(_ nums: [Int],default:0] += 1
 8         }
 9         
10         if k == 0 {
11             return dict.values.reduce(into: 0) { total,appearances in
12                 if appearances > 1 {
13                     total += 1
14                 }
15             }
16         }
17         
18         return dict.keys.reduce(into: 0) { total,num in
19             if dict[num+k,default:0] > 0 {
20                 total += 1
21             }
22             if dict[num-k,default: 0] > 0 {
23                 total += 1
24             }
25             dict[num] = 0
26         }
27         
28     }
29 }

96ms

 1 class Solution {
 2     func findPairs(_ nums: [Int],_ k: Int) -> Int {
 3         guard nums.count > 1 else { return 0}
 4         let sortedNums = nums.sorted()
 5         var behind = 0
 6         var forward = 1
 7         var counter = 0
 8 
 9         while forward < nums.count,behind < nums.count {
10             if behind >= forward {
11                 forward = behind + 1
12                 continue
13             }
14             
15             let diff = abs(sortedNums[forward] - sortedNums[behind])
16             
17             if diff < k {
18                 repeat { forward += 1} while forward < nums.count && sortedNums[forward] == sortedNums[forward-1]
19                 continue
20             }
21 
22             if diff == k {
23                 counter += 1
24                 repeat { forward += 1} while forward < nums.count && sortedNums[forward] == sortedNums[forward-1]
25                 repeat { behind += 1} while behind < nums.count && sortedNums[behind] == sortedNums[behind-1]
26                 continue
27             }
28 
29             if diff > k {
30                 repeat { behind += 1} while behind < nums.count && sortedNums[behind] == sortedNums[behind-1]
31                 continue
32             }
33         }
34         return counter
35     }
36 }

116ms

 1 class Solution {
 2     func findPairs(_ nums: [Int],_ k: Int) -> Int {
 3         let nums =  nums.sorted()
 4         var i = 0
 5         var j = 1
 6         var res = 0
 7         while  i < nums.count && j < nums.count  {
 8             if nums[j] - nums[i] == k {
 9                 res += 1
10                 i += 1
11                 j += 1
12                 while j < nums.count && nums[j] == nums[j-1]  {
13                     j += 1
14                 }
15             }else if nums[j] - nums[i] < k {
16                 j += 1
17             }else  {
18                 i += 1
19                 j = i < j ? j : i+1
20             }
21         }
22         return res
23     }
24 }

132ms

 1 class Solution {
 2     func findPairs(_ nums: [Int],_ k: Int) -> Int {
 3         guard nums.count > 1 else {
 4             return 0
 5         }
 6         var resultSet: [[Int]] = []
 7         var sortedNums = nums
 8         sortedNums.sort()
 9         var firstPointer = 0
10         var secondPointer = 1
11         while secondPointer < sortedNums.count {
12             // print("comparing : (sortedNums[firstPointer]) and (sortedNums[secondPointer])")
13             if abs(sortedNums[firstPointer] - sortedNums[secondPointer]) == k {
14                 var validList: [Int] = [sortedNums[firstPointer],sortedNums[secondPointer]]
15                 // if !resultSet.contains(where: {$0 == validList}) {
16                     resultSet.append(validList)
17                 // }
18                 firstPointer += 1
19             } else if (sortedNums[secondPointer] - sortedNums[firstPointer]) < k {
20                 secondPointer += 1
21             } else {
22                 firstPointer += 1
23             }
24             if firstPointer == secondPointer {
25                 secondPointer += 1
26             }
27         }
28         print("This is the result set : (resultSet)")
29         var removeIndex:[Int] = []
30         if resultSet.count > 1 {
31             for index in 1..<resultSet.count {
32                 // print("index : (index)")
33                 if resultSet[index] == resultSet[index-1] {
34                     removeIndex.append(index)
35                 }
36             }
37         }
38         while removeIndex.count != 0 {
39             // print("removing (removeIndex.last) as (removeIndex)")
40             resultSet.remove(at: removeIndex.last!)
41             let _ = removeIndex.popLast()
42         }
43         return resultSet.count
44     }
45 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!