题目描述
在一个仓库里,有一排条形码,其中第 i
个条形码为 barcodes[i]
。
请你重新排列这些条形码,使其中两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案,此题保证存在答案。
样例
输入:[1,1,1,2,2,2]
输出:[2,1,2,1,2,1]
输入:[1,1,1,1,2,2,3,3]
输出:[1,3,1,3,2,1,2,1]
注意
1 <= barcodes.length <= 10000
1 <= barcodes[i] <= 10000
算法
(思维题) $O(n)$
- 根据抽屉原理,不可能某个数字出现次数超过总数的一半。
- 找到出现次数最多的数字,先将其放到所有的偶数位置 $(0, 2, 4, \dots)$,然后再按照先偶数位然后奇数位的补齐剩余的数字。
时间复杂度
- 使用哈希表统计数字的频率,然后遍历哈希表构造答案,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表和答案。
C++ 代码
class Solution {
private:
int last;
void fill(vector<int> &ans, int x) {
if (last >= ans.size())
last = 1;
ans[last] = x;
last += 2;
}
public:
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
unordered_map<int, int> seen;
int ma = 0, mx;
for (int x : barcodes) {
seen[x]++;
if (ma < seen[x]) {
ma = seen[x];
mx = x;
}
}
const int n = barcodes.size();
last = ma * 2;
vector<int> ans(n);
for (int i = 0; i < ma; i++)
ans[i * 2] = mx;
for (const auto &[k, v] : seen) {
if (k == mx)
continue;
for (int i = 0; i < v; i++)
fill(ans, k);
}
return ans;
}
};
六六六