难度: Medium
在一个仓库里，有一排条形码，其中第 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 <= 100001 <= barcodes[i] <= 10000运行时间: 66 ms
内存: 17.5 MB
class Solution:
def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
n = len(barcodes)
if n <= 2: return barcodes
counts = Counter(barcodes)
eve_idx, odd_idx = 0, 1
half_n = n // 2
ans = [0] * n
for num, cnt in counts.items():
# cnt <= half_n, 优先放在奇数下标
while cnt > 0 and cnt <= half_n and odd_idx < n:
ans[odd_idx] = num
cnt -= 1
odd_idx += 2
# 如果cnt > half_n，必须放在偶数下标
while cnt > 0:
ans[eve_idx] = num
cnt -= 1
eve_idx += 2
return ans
这个题解使用了贪心算法和计数方法来重新排列条形码，以确保没有两个相邻的条形码是相同的。首先，使用Counter计算每个条形码出现的次数。然后，通过遍历这个计数字典，将条形码按照出现次数插入到结果列表中的适当位置。代码中使用了两个索引，odd_idx（奇数索引）和eve_idx（偶数索引），来分别填充奇数和偶数位置的条形码。如果某个条形码的计数小于等于n的一半，则优先填充到奇数位置；如果超过n的一半，则填充到偶数位置。这种策略保证了最终结果中任何相邻位置都不会有相同的条形码。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
n = len(barcodes)
if n <= 2: return barcodes
counts = Counter(barcodes) # 计数各个条形码的出现次数
eve_idx, odd_idx = 0, 1 # 初始化偶数和奇数索引
half_n = n // 2 # n的一半
ans = [0] * n # 初始化结果数组
for num, cnt in counts.items():
while cnt > 0 and cnt <= half_n and odd_idx < n:
ans[odd_idx] = num # 填充奇数位置
cnt -= 1
odd_idx += 2
while cnt > 0:
ans[eve_idx] = num # 填充偶数位置
cnt -= 1
eve_idx += 2
return ans
贪心算法在此题中的应用是为了尽可能地分散高频条形码的位置，以避免相邻。通过计数方法，我们能够明确每个条形码的出现频率，然后通过贪心地选择位置（奇数位或偶数位）来放置这些条形码。对于出现次数最多的条形码，尽量分布在整个数组中，从而使得任何两个相邻的位置尽可能不放置相同的条形码。这种方法直观且有效地解决了问题，确保了算法的高效性和问题的正确解决。
当某个条形码的计数超过n的一半时，将它们优先填充到偶数位置是为了确保这些条形码可以尽可能均匀地分布在整个数组中。考虑到偶数索引（0, 2, 4, ...）在数组中是连续的，而且对于偶数n来说，偶数位置的数量等于奇数位置的数量。如果条形码的数量非常多，放在偶数位可以保证这些位置被填满，余下的可以填入奇数位置，从而避免连续相同条形码的情况。
当n是奇数时，奇数索引（1, 3, 5, ...）的数量确实会比偶数索引（0, 2, 4, ...）多一个。这意味着最后一个条形码将被放置在最后一个奇数索引上。这种情况下，如果最后几个条形码是相同的，它们可能无法完全分散，因为奇数位置多一个。然而，算法通过优先填充偶数位置确保了高频条形码的分散，因此最终的排列仍然能够尽可能避免相邻条形码相同，即使在奇数总数的情况下。
在代码中，`cnt <= half_n`的条件是基于将低频条形码优先放置在奇数位置的考虑。这是因为如果一个条形码的数量不超过n的一半，意味着即使完全填满所有奇数位置，也不会导致任何相邻位置出现相同的条形码。这样的策略帮助确保了条形码的均匀分布，尤其是在条形码种类较多的情况下。这也是一种贪心策略，通过优先解决可能性较低的问题（即低频条形码的分布），从而简化了问题的复杂性。