原文链接: https://leetcode-cn.com/problems/distant-barcodes

英文原文

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 <= 10000
• 1 <= barcodes[i] <= 10000

中文题目

在一个仓库里，有一排条形码，其中第 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. 1 <= barcodes.length <= 10000
2. 1 <= barcodes[i] <= 10000

 

通过代码

高赞题解

分析：

要想让相邻的元素不重复那么可以将相同的元素间隔一个一字儿排开，排到末尾再从头开始填空就行。

对于题目给的例子[1,1,1,1,2,2,3,3]，分两步完成:

1. [1, _, 1, _, 1, _, 1, _] 其中_表示还未填写
2. [1, 2, 1, 2, 1, 3, 1, 4]

这样就能保证一定不会有连续的元素存在。题目已经保证了一定存在解法。那我们需要做的是按照元素出现的次数由多到少排序好进而进行间隔插入。代码如下:

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counter = dict(collections.Counter(barcodes))
        #按出现次数统计元素
        sortedCounter = sorted( counter, key=lambda k: 0 - counter[k])
        barcodes = []
        #重新排序
        for i in sortedCounter:
            barcodes += [i] * counter[i]
        
        arrangedBarcodes = [None for _ in range(len(barcodes))]
        #间隔插入
        arrangedBarcodes[::2] = barcodes[:len(arrangedBarcodes[::2])]
        arrangedBarcodes[1::2] = barcodes[len(arrangedBarcodes[::2]):]

        return arrangedBarcodes

统计信息

通过次数	提交次数	AC比率
8291	21827	38.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言