跳转至

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

解法

方法一：计数 + 排序

思考

相邻不能相同，出现次数最多的值不超过 \(\lceil n/2\rceil\) 时一定有解。把高频值尽量隔开放，先铺偶数下标再铺奇数下标即可错开。

按频次降序、值升序排列，使相同数相邻且高频在前，再把前一半写入偶数位、后一半写入奇数位。

这样最频繁的值优先占据相隔的偶数槽，不会与自己相邻。

我们先用哈希表或数组 \(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;
}

评论