leetcode 1054 距离相等的条形码

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

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

示例 1：

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

示例 2：

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

提示：

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

思路是：

先对出现的次数进行统计，先安排出现次数最多的，先间隔排奇数，避免出现排到时已经错过唯一的机会。然后再在剩下的偶数位置排剩下的。

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        from collections import defaultdict
        if len(barcodes) <= 1:
            return barcodes
        count = defaultdict(int)
        for bar in barcodes:
            count[bar] += 1
        count = sorted(count.items(), key=lambda x: x[1], reverse=True)
        barcodes = []
        for i, c in count:
            barcodes += [i] * c
        mid = len(barcodes) // 2
        odd = len(barcodes) % 2
        result = [0] * len(barcodes)
        for i, bar in zip(range(0, len(barcodes), 2), barcodes[:mid + odd]):
            result[i] = bar
        for i, bar in zip(range(1, len(barcodes), 2), barcodes[mid + odd:]):
            result[i] = bar
        return result