跳转至

1054. 距离相等的条形码

题目描述

在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。

请你重新排列这些条形码，使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案，此题保证存在答案。

 

示例 1：

输入：barcodes = [1,1,1,2,2,2]
输出：[2,1,2,1,2,1]

示例 2：

输入：barcodes = [1,1,1,1,2,2,3,3]
输出：[1,3,1,3,2,1,2,1]

 

提示：

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

解法

方法一：计数 + 排序

我们先用哈希表或数组 \(cnt\) 统计数组 \(barcodes\) 中各个数出现的次数，然后将 \(barcodes\) 中的数按照它们在 \(cnt\) 中出现的次数从大到小排序，如果出现次数相同，那么就按照数的大小从小到大排序（确保相同的数相邻）。

接下来，我们创建一个长度为 \(n\) 的答案数组 \(ans\)，然后遍历排好序的 \(barcodes\)，将元素依次填入答案数组的 \(0, 2, 4, \cdots\) 等偶数下标位置，然后将剩余元素依次填入答案数组的 \(1, 3, 5, \cdots\) 等奇数下标位置即可。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(M)\)。其中 \(n\) 和 \(M\) 分别是数组 \(barcodes\) 的长度以及数组 \(barcodes\) 中的最大值。

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;
}

评论