当前位置：首页 > article >正文

【数据结构-堆】力扣1054. 距离相等的条形码

article 2025/3/1 10:07:13

在一个仓库里，有一排条形码，其中第 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

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        //条形码 数量
        unordered_map<int, int> counts;
        int n = barcodes.size();
        for(int i = 0; i < n; i++){
            counts[barcodes[i]]++;
        }

        priority_queue<pair<int, int>> q;
        for(auto &[x, cx] : counts){
            q.push({cx, x});
        }

        vector<int> res;
        while(q.size() > 1){
            auto [cx1, x1] = q.top();
            q.pop();
            auto [cx2, x2] = q.top();
            q.pop();

            res.push_back(x1);
            res.push_back(x2);

            cx1--;
            cx2--;

            if(cx1 > 0){
                q.push({cx1, x1});
            }

            if(cx2 > 0){
                q.push({cx2, x2});
            }
        }

        if(!q.empty()){
            res.push_back(q.top().second);
        }
        
        return res;
    }
};