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,1,2,1,2]

约束条件：

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

提示：

  • 我们总是希望选择出现次数最多或第二多的元素来写入下一个位置。什么数据结构可以让我们高效地查询这个信息？

解题思路

这道题的核心思想是贪心算法配合优先队列（最大堆）。

解题思路：

  1. 频次统计：首先统计每个条形码出现的次数
  2. 优先队列：使用最大堆存储 (频次, 条形码值) 对，确保频次高的元素优先被选择
  3. 贪心策略：每次选择频次最高的条形码放入结果，但要确保不与前一个相同
  4. 轮换机制：为避免相邻重复，我们需要在最高频次和次高频次的元素间轮换

具体算法：

  • 如果堆顶元素与上一个选择的元素不同，直接选择堆顶
  • 如果相同，则选择频次第二高的元素
  • 每次选择后，将该元素频次减1，如果频次仍大于0则重新入堆
  • 重复直到所有元素都被安排

这种方法保证了我们总是优先处理频次高的元素，同时避免相邻重复，时间复杂度为O(n log k)，其中k是不同条形码的种类数。

还有一种基于计数排序的方法，时间复杂度更优，但实现稍复杂。对于此题规模，优先队列方法已足够高效。

代码实现

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int, int> count;
        for (int code : barcodes) {
            count[code]++;
        }
        
        priority_queue<pair<int, int>> pq;
        for (auto& p : count) {
            pq.push({p.second, p.first});
        }
        
        vector<int> result;
        while (!pq.empty()) {
            auto first = pq.top();
            pq.pop();
            
            if (result.empty() || result.back() != first.second) {
                result.push_back(first.second);
                if (first.first > 1) {
                    pq.push({first.first - 1, first.second});
                }
            } else {
                auto second = pq.top();
                pq.pop();
                result.push_back(second.second);
                if (second.first > 1) {
                    pq.push({second.first - 1, second.second});
                }
                pq.push(first);
            }
        }
        
        return result;
    }
};

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        from collections import Counter
        import heapq
        
        count = Counter(barcodes)
        heap = [(-freq, code) for code, freq in count.items()]
        heapq.heapify(heap)
        
        result = []
        while heap:
            first = heapq.heappop(heap)
            
            if not result or result[-1] != first[1]:
                result.append(first[1])
                if first[0] < -1:
                    heapq.heappush(heap, (first[0] + 1, first[1]))
            else:
                second = heapq.heappop(heap)
                result.append(second[1])
                if second[0] < -1:
                    heapq.heappush(heap, (second[0] + 1, second[1]))
                heapq.heappush(heap, first)
        
        return result

public class Solution {
    public int[] RearrangeBarcodes(int[] barcodes) {
        var count = new Dictionary<int, int>();
        foreach (int code in barcodes) {
            count[code] = count.GetValueOrDefault(code, 0) + 1;
        }
        
        var pq = new PriorityQueue<(int freq, int code), int>();
        foreach (var kvp in count) {
            pq.Enqueue((kvp.Value, kvp.Key), -kvp.Value);
        }
        
        var result = new List<int>();
        while (pq.Count > 0) {
            var first = pq.Dequeue();
            
            if (result.Count == 0 || result[result.Count - 1] != first.code) {
                result.Add(first.code);
                if (first.freq > 1) {
                    pq.Enqueue((first.freq - 1, first.code), -(first.freq - 1));
                }
            } else {
                var second = pq.Dequeue();
                result.Add(second.code);
                if (second.freq > 1) {
                    pq.Enqueue((second.freq - 1, second.code), -(second.freq - 1));
                }
                pq.Enqueue(first, -first.freq);
            }
        }
        
        return result.ToArray();
    }
}

var rearrangeBarcodes = function(barcodes) {
    const freq = new Map();
    for (const code of barcodes) {
        freq.set(code, (freq.get(code) || 0) + 1);
    }
    
    const sorted = Array.from(freq.entries()).sort((a, b) => b[1] - a[1]);
    const result = new Array(barcodes.length);
    
    let index = 0;
    for (const [code, count] of sorted) {
        for (let i = 0; i < count; i++) {
            result[index] = code;
            index += 2;
            if (index >= barcodes.length) {
                index = 1;
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log k)，其中 n 是条形码总数，k 是不同条形码的种类数。需要进行 n 次堆操作，每次操作的时间复杂度为 O(log k)
空间复杂度O(k)，用于存储哈希表和优先队列，其中 k 是不同条形码的种类数