[Swift]LeetCode1054.距离相等的条形码 | Distant Barcodes
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
In a warehouse, there is a row of barcodes, where the i-th barcode is barcodes[i].
Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.
Example 1:
Input: [1,1,1,2,2,2] Output: [2,1,2,1,2,1]
Example 2:
Input: [1,1,1,1,2,2,3,3] Output: [1,3,1,3,2,1,2,1]
Note:
1 <= barcodes.length <= 100001 <= barcodes[i] <= 10000
在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。
请你重新排列这些条形码，使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案，此题保证存在答案。
示例 1：
输入：[1,1,1,2,2,2] 输出：[2,1,2,1,2,1]
示例 2：
输入：[1,1,1,1,2,2,3,3] 输出：[1,3,1,3,2,1,2,1]
提示：
1 <= barcodes.length <= 100001 <= barcodes[i] <= 10000
Runtime: 476 ms
Memory Usage: 22.2 MB
1 class Solution {
2 func rearrangeBarcodes(_ barcodes: [Int]) -> [Int] {
3 let n:Int = barcodes.count
4 var cnt:[Int] = [Int](repeating: 0, count: 10005)
5 var ret:[Int] = [Int](repeating: 0, count: n)
6 for i in 0..<n
7 {
8 cnt[barcodes[i]] += 1
9 }
10 var mx:Int = 0
11 var id:Int = 0
12 for i in 1...10000
13 {
14 if cnt[i]>mx
15 {
16 mx = cnt[i]
17 id = i
18 }
19 }
20 var j:Int = 0
21 while(j < n)
22 {
23 if cnt[id] > 0
24 {
25 cnt[id] -= 1
26 ret[j] = id
27 }
28 else
29 {
30 break
31 }
32 j += 2
33 }
34 if j >= n {j = 1}
35 for i in 1...10000
36 {
37 while(cnt[i] > 0)
38 {
39 cnt[i] -= 1
40 ret[j]=i
41 j+=2
42 if j >= n
43 {
44 j = 1
45 }
46 }
47 }
48 return ret
49 }
50 }672ms
1 class Solution {
2 func rearrangeBarcodes(_ barcodes: [Int]) -> [Int] {
3
4 var map = [Int: Int]()
5 for code in barcodes {
6 map[code] = map[code, default: 0] + 1
7 }
8 let sortKeys = map.keys.sorted { map[$0]! > map[$1]! }
9 var i = 0, ans = barcodes
10 for k in sortKeys {
11 for j in 0..<map[k]! {
12 ans[i] = k
13 i += 2
14 if i >= barcodes.count { i = 1 }
15 }
16 }
17 return ans
18 }
19 }700ms
1 class Solution {
2 func rearrangeBarcodes(_ barcodes: [Int]) -> [Int] {
3 guard barcodes.count > 1 else { return barcodes }
4
5 var counts = [Int: Int]()
6
7 for barcode in barcodes {
8 counts[barcode] = counts[barcode, default: 0] + 1
9 }
10
11 let unique = counts.keys.sorted { (k1, k2) -> Bool in
12 return counts[k1]! > counts[k2]!
13 }
14
15 var results = [[Int]]()
16
17 let most = unique[0]
18
19 for _ in 0..<counts[most]! {
20 results.append([most])
21 }
22
23 var p = 0
24 for i in 1..<unique.count {
25 let key = unique[i]
26 let c = counts[key]!
27
28 for _ in 0..<c {
29 results[p].append(key)
30 p = (p + 1) % results.count
31 }
32 }
33
34 var result = [Int]()
35
36 for a in results {
37 result += a
38 }
39
40 return result
41 }
42 }708ms
1 class Solution {
2 func rearrangeBarcodes(_ barcodes: [Int]) -> [Int] {
3 var res = Array(repeating: 0, count: barcodes.count)
4 var map: [Int: Int] = [:]
5 for b in barcodes {
6 map[b] = (map[b] ?? 0) + 1
7 }
8
9 var sortd = map.keys.sorted {
10 map[$0]! > map[$1]!
11 }
12
13 print(sortd)
14 var i = 0
15 var sortdInd = 0
16 while i < res.count {
17 res[i] = sortd[sortdInd];
18 if map[sortd[sortdInd]]! - 1 == 0 {
19 sortdInd += 1
20 } else {
21 map[sortd[sortdInd]] = map[sortd[sortdInd]]! - 1
22 }
23 i += 2
24 if i >= res.count && i % 2 == 0 {
25 i = 1
26 }
27 }
28 return res
29 }
30 }