题目
在一个仓库里，有一排条形码，其中第 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，将零碎时间利用起来】
