Formatted question description: https://leetcode.ca/all/1054.html
1054. Distant Barcodes (Medium)
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
Solution 1. Greedy + Heap
// OJ: https://leetcode.com/problems/distant-barcodes/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
vector<int> rearrangeBarcodes(vector<int>& A) {
unordered_map<int, int> cnt;
for (int n : A) cnt[n]++;
auto cmp = [&](int a, int b) { return cnt[a] < cnt[b]; };
priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
for (auto &p : cnt) q.push(p.first);
int prev = 0;
vector<int> ans;
while (q.size()) {
int n = q.top();
q.pop();
ans.push_back(n);
if (prev) q.push(prev);
if (--cnt[n]) prev = n;
else prev = 0;
}
return ans;
}
};
Solution 2. Interleaving Placement
// OJ: https://leetcode.com/problems/distant-barcodes/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
vector<int> rearrangeBarcodes(vector<int>& A) {
unordered_map<int, int> cnt;
set<pair<int, int>> s;
for (int n : A) cnt[n]++;
for (auto &p : cnt) s.emplace(p.second, p.first);
int j = 0, N = A.size();
vector<int> ans(N);
for (auto it = s.rbegin(); it != s.rend(); ++it) {
for (int c = 0; c < it->first; ++c, j += 2) {
if (j >= N) j = 1;
ans[j] = it->second;
}
}
return ans;
}
};
Solution 3.
Just fill the most frequent number first. The others can be filled irrespective of their frequency.
// OJ: https://leetcode.com/problems/distant-barcodes/
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<int> rearrangeBarcodes(vector<int>& A) {
short cnt[10001] = {}, maxCnt = 0, num = 0, j = 0;
for (int n : A) {
maxCnt = max(maxCnt, ++cnt[n]);
if (maxCnt == cnt[n]) num = n;
}
for (int i = 0; i <= 10000; ++i) {
int n = i ? i : num;
while (cnt[n]-- > 0) {
A[j] = n;
j = (j + 2) % A.size();
if (j == 0) j = 1;
}
}
return A;
}
};
Java
class Solution {
public int[] rearrangeBarcodes(int[] barcodes) {
int[] counts = new int[10001];
int maxCount = 0;
int length = barcodes.length;
for (int i = 0; i < length; i++) {
int num = barcodes[i];
counts[num]++;
maxCount = Math.max(maxCount, counts[num]);
}
int[] rearrangeBarcodes = new int[length];
int evenIndex = 0, oddIndex = 1;
int maxPossible = length / 2 + 1;
for (int i = 1; i <= 10000; i++) {
while (counts[i] > 0 && counts[i] < maxPossible && oddIndex < length) {
rearrangeBarcodes[oddIndex] = i;
counts[i]--;
oddIndex += 2;
}
while (counts[i] > 0) {
rearrangeBarcodes[evenIndex] = i;
counts[i]--;
evenIndex += 2;
}
}
return rearrangeBarcodes;
}
}