[Swift]LeetCode954.二倍数对数组|ArrayofDoubledPairs

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

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

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

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

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

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

Given an array of integers A with even length, return true if and only if it is possible to reorder it such that A[2 * i + 1] = 2 * A[2 * i] for every 0 <= i < len(A) / 2.

Example 1:

Input: [3,1,3,6]
Output: false

Example 2:

Input: [2,1,2,6]
Output: false

Example 3:

Input: [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

Example 4:

Input: [1,2,4,16,8,4]
Output: false

Note:

0 <= A.length <= 30000
A.length is even
-100000 <= A[i] <= 100000

给定一个长度为偶数的整数数组 A，只有对 A 进行重组后可以满足 “对于每个 0 <= i < len(A) / 2，都有 A[2 * i + 1] = 2 * A[2 * i]” 时，返回 true；否则，返回 false。

示例 1：

输入：[3,1,3,6]
输出：false

示例 2：

输入：[2,1,2,6]
输出：false

示例 3：

输入：[4,-2,2,-4]
输出：true
解释：我们可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]

示例 4：

输入：[1,2,4,16,8,4]
输出：false

提示：

0 <= A.length <= 30000
A.length 为偶数
-100000 <= A[i] <= 100000

688ms

 1 class Solution {
 2     func canReorderDoubled(_ A: [Int]) -> Bool {
 3         var d = [Int: Int]()
 4         for a in A {
 5             d[a, default: 0] += 1
 6         }
 7         let ps = Array(d.keys).filter {$0 > 0}.sorted()
 8         let ns = Array(d.keys).filter {$0 < 0}.sorted {$0 > $1}
 9         for p in ps {
10             //print(d)
11             guard let u = d[p], u >= 0 else {
12                 return false
13             }
14             d[2*p, default: 0] -= u
15             d[p] = 0
16         }
17         for n in ns {
18             //print(d, n)
19             guard let u = d[n], u >= 0 else {
20                 return false
21             }
22             d[2*n, default: 0] -= u
23             d[n] = 0
24         }
25         guard d[0, default: 0] % 2 == 0 else {
26             return false
27         }
28         d[0] = 0
29         let c = Array(d.values).filter {$0 != 0}.count
30         guard c == 0 else {
31             return false
32         }
33         return true
34     }
35 }

788ms

 1 class Solution {
 2     func canReorderDoubled(_ A: [Int]) -> Bool {
 3         var d = [Int: Int]()
 4         for a in A {
 5             d[abs(a), default: 0] += 1
 6         }
 7         let ps = Array(d.keys).sorted()
 8         for p in ps {
 9             guard d[p*2, default: 0] >= d[p]! else {
10                 return false
11             }
12             d[2*p, default: 0] -= d[p]!
13         }
14         return true
15     }
16 }

1076ms

 1 class Solution {
 2     func canReorderDoubled(_ A: [Int]) -> Bool {
 3      if A.count == 0 {
 4         return true
 5     }
 6     if A.count % 2 != 0 {
 7         return false
 8     }
 9     
10     let A = A.sorted()
11     
12     var memo = [Int: Int]()
13     for i in 0..<A.count {
14         let current = A[i]
15         
16         if let value = memo[current * 2] {
17             if value - 1 == 0 {
18                 memo.removeValue(forKey: current * 2)
19             } else {
20                 memo[current * 2] = value - 1
21             }
22         } else if current % 2 == 0, let value = memo[current / 2] {
23             if value - 1 == 0 {
24                 memo.removeValue(forKey: current / 2)
25             } else {
26                 memo[current / 2] = value - 1
27             }
28         } else {
29             memo[current] = (memo[current] ?? 0) + 1
30         }
31         
32     }
33     
34     return memo.count == 0
35     }
36 }

1100ms

 1 class Solution {
 2     func canReorderDoubled(_ A: [Int]) -> Bool {
 3         var n:Int = A.count
 4         var a:[Int] = [Int](repeating:0,count:n)
 5         for i in 0..<n
 6         {
 7             if A[i] < 0
 8             {
 9                 a[i] = -A[i]*100000000
10             }
11             else
12             {
13                 a[i] = A[i]
14             }
15         }
16         a = a.sorted(by: <)
17         var p:Int = 0
18         var done:[Bool] = [Bool](repeating:false,count:n)
19         for i in 0..<n
20         {
21             if !done[i]
22             {
23                 done[i] = true
24                 while(p < n && (a[p] != a[i] * 2 || done[p]))
25                 {
26                     p += 1
27                 }
28                 if p == n {return false}
29                 done[p] = true
30             }
31         }
32         return true
33     }
34 }

1316ms

 1 class Solution {
 2     func canReorderDoubled(_ A: [Int]) -> Bool {
 3         var arr = A.filter { $0 <= 0 }.sorted().reversed() + A.filter { $0 > 0 }.sorted()
 4         var unused = [Int: Int]()
 5         var used = [Int: Int]()
 6         
 7         for a in arr {
 8             unused[a] = (unused[a] ?? 0) + 1
 9         }
10         
11         for a in arr {
12             if let c = used[a] {
13                 if c == 1 {
14                     used.removeValue(forKey: a)
15                 } else {
16                     used[a] = c - 1
17                 }
18             } else {
19                 unused[a] = unused[a]! - 1
20                 if unused[a] == 0 { unused.removeValue(forKey: a) }
21                 if let c = unused[a * 2] {
22                     if c == 1 {
23                         unused.removeValue(forKey: a * 2)
24                     } else {
25                         unused[a * 2] = c - 1
26                     }
27                     used[a * 2] = (used[a * 2] ?? 0) + 1
28                 } else {
29                     return false
30                 }
31             }
32         }
33         
34         return true
35     }
36 }

1340ms

 1 class Solution {
 2     func canReorderDoubled(_ A: [Int]) -> Bool {
 3         let aSortedPositive = A.filter{ $0 >= 0 }.sorted(by:{ $0 > $1} )
 4         let aSortedNegative = A.filter{ $0 < 0 }.sorted(by:{ $0 < $1} )
 5         let positiveMatches = checkItems(aSortedPositive)
 6         let negativeMatches = checkItems(aSortedNegative)
 7 
 8         if positiveMatches && negativeMatches {
 9             return true
10         } else {
11             return false
12         }
13     }
14     
15     private func checkItems(_ A: [Int]) -> Bool {
16         var pendingNumbers = [Int: Int]()
17 
18         for item in A {
19             let theDoubleExists = (pendingNumbers[item * 2] != nil)
20             let theHalfExists = (item%2 == 0 && pendingNumbers[item / 2] != nil)
21             
22             if theDoubleExists {
23                 var newDoubleCount = pendingNumbers[item * 2]! - 1
24                 if newDoubleCount == 0 {
25                    pendingNumbers.removeValue(forKey:item * 2)
26                 } else {
27                     pendingNumbers[item * 2] = newDoubleCount                                        
28                 }
29             } else if theHalfExists {
30                 var newHalfCount = pendingNumbers[item / 2]! - 1
31                 if newHalfCount == 0 {
32                     pendingNumbers.removeValue(forKey:item / 2)
33                 } else {
34                 pendingNumbers[item / 2] = newHalfCount                                        
35                 }
36 
37             } else {
38                 var newCount = (pendingNumbers[item] ?? 0) + 1
39                 pendingNumbers[item] = newCount
40             }
41         
42         }
43                     
44         if pendingNumbers.count == 0 {
45             return true
46         } else {
47             return false            
48         }
49     }
50 }

1908ms

 1 class Solution {
 2     func canReorderDoubled(_ A: [Int]) -> Bool {
 3         return checkItems(A.sorted(by:{ abs($0) > abs($1)}))
 4     }
 5     
 6     private func checkItems(_ A: [Int]) -> Bool {
 7         var pendingNumbers = [Int: Int]()
 8 
 9         for item in A {
10             let theDoubleCount = pendingNumbers[item * 2]
11             let theDoubleExists = (theDoubleCount != nil && theDoubleCount != 0)
12             
13             if theDoubleExists {
14                 pendingNumbers[item * 2] = theDoubleCount! - 1
15             } else {
16                 var newCount = (pendingNumbers[item] ?? 0) + 1
17                 pendingNumbers[item] = newCount
18             }
19         }
20         
21         let remainingNumbers = pendingNumbers.filter{ $0.value != 0 }
22 
23         if remainingNumbers.count == 0 {
24             return true
25         } else {
26             return false            
27         }
28     }
29 }

2036ms

 1 class Solution {
 2     func canReorderDoubled(_ A: [Int]) -> Bool {
 3         guard A.count > 0 else { return true }
 4         var sortedA = A.sorted()
 5         var sortedNegA: [Int] = []
 6         var map: [Int: Int] = [:]
 7         for a in A {
 8             map[a] = (map[a] ?? 0) + 1
 9         }
10         
11         if sortedA[0] < 0 {
12             var i = 0
13             while i < sortedA.count {
14                 if sortedA[i] < 0 { 
15                     sortedNegA.append(sortedA[i]) 
16                     sortedA.remove(at: i)
17                 } else {
18                     break
19                 }
20             }
21         }
22         
23         sortedNegA = Array(sortedNegA.reversed())
24         //print(sortedA)
25         //print(sortedNegA)
26         var i = 0
27         while i < sortedNegA.count {
28             defer { i += 1}
29             guard (map[sortedNegA[i]] ?? 0) > 0 else { continue }
30             if (map[sortedNegA[i] * 2] ?? 0) > 0 {
31                 map[sortedNegA[i] * 2] = map[sortedNegA[i] * 2]! - 1
32                 map[sortedNegA[i]] = map[sortedNegA[i]]! - 1
33             } else {
34                 return false
35             }
36         }
37         
38         i = 0
39         while i < sortedA.count {
40             defer { i += 1}
41             guard (map[sortedA[i]] ?? 0) > 0 else { continue }
42             if (map[sortedA[i] * 2] ?? 0) > 0 {
43                 map[sortedA[i] * 2] = map[sortedA[i] * 2]! - 1
44                 map[sortedA[i]] = map[sortedA[i]]! - 1
45             } else {
46                 return false
47             }
48         }
49         
50         return true
51     }
52 }