# 1054. Distant Barcodes

In a warehouse, there is a row of barcodes, where the `ith` 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: barcodes = [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]
``````

Example 2:

``````Input: barcodes = [1,1,1,1,2,2,3,3]
Output: [1,3,1,3,1,2,1,2]
``````

Constraints:

• `1 <= barcodes.length <= 10000`
• `1 <= barcodes[i] <= 10000`

``````class Solution {
public:
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
vector<int> res;
priority_queue<pair<int, int>> pq;
unordered_map<int, int> numCnt;
for (int num : barcodes) ++numCnt[num];
for (auto &a : numCnt) {
pq.push({a.second, a.first});
}
while (pq.size() > 1) {
auto a = pq.top(); pq.pop();
auto b = pq.top(); pq.pop();
res.push_back(a.second);
res.push_back(b.second);
if (--a.first > 0) pq.push(a);
if (--b.first > 0) pq.push(b);
}
if (!pq.empty()) res.push_back(pq.top().second);
return res;
}
};
``````

``````class Solution {
public:
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
int n = barcodes.size(), pos = 0;
vector<int> res(n);
vector<pair<int, int>> vec;
unordered_map<int, int> numCnt;
for (int num : barcodes) ++numCnt[num];
for (auto &a : numCnt) {
vec.push_back({a.second, a.first});
}
sort(vec.rbegin(), vec.rend());
for (auto &a : vec) {
for (int i = 0; i < a.first; ++i, pos += 2) {
if (pos >= n) pos = 1;
res[pos] = a.second;
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1054

https://leetcode.com/problems/distant-barcodes/

https://leetcode.com/problems/distant-barcodes/discuss/299371/C%2B%2B-with-picture-O(N)

https://leetcode.com/problems/distant-barcodes/discuss/299225/JavaPython-Set-Odd-Position-and-Even-Position

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation