[Swift]LeetCode954. 二倍数对数组 | Array of Doubled Pairs
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10090740.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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 <= 30000A.lengthis 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 <= 30000A.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 }