题目

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

思路

先用字典存储每个元素的频次，再按频次对字典每个元素构建最大堆，堆顶就是出现次数最多的元素。接着遍历堆，隔一个空填一个元素。

解答

class Solution {
public:
    typedef pair<int, int> mypair;  
    struct cmp{  //自定义堆的排序方法
        bool operator()(const mypair& left, const mypair& right){
            return left.second < right.second;
        }
    };
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        int size = barcodes.size();
        mypair temp;  //填空时使用
        vector<int> ans(size, 0);
        unordered_map<int, int> hash;
        priority_queue<mypair, vector<mypair>, cmp> que; //最大堆
        
        for(auto i : barcodes) hash[i]++;  //统计频次
        for(auto iter : hash) que.push(iter);  //入堆
        int i = 0;  //填空时的坐标索引
        while(!que.empty()){
            temp = que.top();
            for(int j=0; j<temp.second; j++){
                ans[i] = temp.first;
                i = (i + 2 >= size) ? 1 : i + 2; // 隔一位填充一个
            }
            que.pop();
        }
        return ans;
    }
};

【关注公众号DoCode，每日一道LeetCode，将零碎时间利用起来】