Description
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 <= 100001 <= barcodes[i] <= 10000
Solutions
Solution 1: Counting + Sorting
First, we use a hash table or array cnt to count the number of occurrences of each number in the array barcodes. Then, we sort the numbers in barcodes according to their occurrence times in cnt from large to small. If the occurrence times are the same, we sort them from small to large (to ensure the same numbers are adjacent).
Next, we create an answer array ans of length n. We traverse the sorted barcodes, and sequentially fill the elements into the even index positions 0, 2, 4, … of the answer array. Then, we fill the remaining elements into the odd index positions 1, 3, 5, … of the answer array.
The time complexity is O(n × log n), and the space complexity is O(M). Where n and M are the length of the array barcodes and the maximum value in the array barcodes, respectively.
PythonJavaC++GoTypeScript
class Solution:
def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
cnt = Counter(barcodes)
barcodes.sort(key=lambda x: (-cnt[x], x))
n = len(barcodes)
ans = [0] * len(barcodes)
ans[::2] = barcodes[: (n + 1) // 2]
ans[1::2] = barcodes[(n + 1) // 2 :]
return ans(code-box)
class Solution {
public int[] rearrangeBarcodes(int[] barcodes) {
int n = barcodes.length;
Integer[] t = new Integer[n];
int mx = 0;
for (int i = 0; i < n; ++i) {
t[i] = barcodes[i];
mx = Math.max(mx, barcodes[i]);
}
int[] cnt = new int[mx + 1];
for (int x : barcodes) {
++cnt[x];
}
Arrays.sort(t, (a, b) -> cnt[a] == cnt[b] ? a - b : cnt[b] - cnt[a]);
int[] ans = new int[n];
for (int k = 0, j = 0; k < 2; ++k) {
for (int i = k; i < n; i += 2) {
ans[i] = t[j++];
}
}
return ans;
}
}(code-box)
class Solution {
public:
vector<int> rearrangeBarcodes(vector<int>& barcodes) {
int mx = *max_element(barcodes.begin(), barcodes.end());
int cnt[mx + 1];
memset(cnt, 0, sizeof(cnt));
for (int x : barcodes) {
++cnt[x];
}
sort(barcodes.begin(), barcodes.end(), [&](int a, int b) {
return cnt[a] > cnt[b] || (cnt[a] == cnt[b] && a < b);
});
int n = barcodes.size();
vector<int> ans(n);
for (int k = 0, j = 0; k < 2; ++k) {
for (int i = k; i < n; i += 2) {
ans[i] = barcodes[j++];
}
}
return ans;
}
};(code-box)
func rearrangeBarcodes(barcodes []int) []int {
mx := slices.Max(barcodes)
cnt := make([]int, mx+1)
for _, x := range barcodes {
cnt[x]++
}
sort.Slice(barcodes, func(i, j int) bool {
a, b := barcodes[i], barcodes[j]
if cnt[a] == cnt[b] {
return a < b
}
return cnt[a] > cnt[b]
})
n := len(barcodes)
ans := make([]int, n)
for k, j := 0, 0; k < 2; k++ {
for i := k; i < n; i, j = i+2, j+1 {
ans[i] = barcodes[j]
}
}
return ans
}(code-box)
function rearrangeBarcodes(barcodes: number[]): number[] {
const mx = Math.max(...barcodes);
const cnt = Array(mx + 1).fill(0);
for (const x of barcodes) {
++cnt[x];
}
barcodes.sort((a, b) => (cnt[a] === cnt[b] ? a - b : cnt[b] - cnt[a]));
const n = barcodes.length;
const ans = Array(n);
for (let k = 0, j = 0; k < 2; ++k) {
for (let i = k; i < n; i += 2, ++j) {
ans[i] = barcodes[j];
}
}
return ans;
}(code-box)
