[Swift]LeetCode1054.距离相等的条形码|DistantBarcodes

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

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

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

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

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

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

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 <= 10000
1 <= 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 <= 10000
1 <= 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 }