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#
1
2
3
4
5
6
7
8
9
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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;
}
|
