题目链接
英文链接:https://leetcode.com/problems/distant-barcodes/
中文链接:https://leetcode-cn.com/problems/distant-barcodes/
题目详述
在一个仓库里,有一排条形码,其中第 i 个条形码为 barcodes[i]。
请你重新排列这些条形码,使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案,此题保证存在答案。
示例 1:
1 | 输入:[1,1,1,2,2,2] |
示例 2:
1 | 输入:[1,1,1,1,2,2,3,3] |
提示:
- 1 <= barcodes.length <= 10000
- 1 <= barcodes[i] <= 10000
题目详解
- 题目保证存在答案。
- 可以按照这种贪心原则来安排顺序:统计每个数的出现次数,按照出现次数从大到小排序。然后用它们依次填充下标 0、2、4……位置,再填充下标 1、3、5……位置。
- 时间复杂度为
O(nlogn)
,时间主要花在排序上。
1 | public class LeetCode_01054 { |
- 实际上可以不用排序,只用把出现次数最多的数排好,其他的数的相对顺序可以是任意的。
- 时间复杂度为
O(n)
。
1 | public class LeetCode_01054 { |