• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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. 1 <= barcodes.length <= 10000
  2. 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. 1 <= barcodes.length <= 10000
  2. 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode44.通配符匹配|WildcardMatching发布时间:2022-07-13
下一篇:
使用Swift操作NSDate类型基础发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap