1054. 间隔相等的条形码
关键词：计数、哈希表
题目起源：1054. 间隔相等的条形码 - 力扣（Leetcode）
题目形容
T计数 T哈希表在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。
请你重新排列这些条形码，使其中任意两个相邻的条形码不能相等。 你能够返回任何满足该要求的答案，此题保障存在答案。
输出：barcodes = [1,1,1,2,2,2]输入：[2,1,2,1,2,1]输出：barcodes = [1,1,1,1,2,2,3,3]输入：[1,3,1,3,2,1,2,1]数据范畴1 <= barcodes.length <= 100001 <= barcodes[i] <= 10000优先队列
直观上来看，咱们应该尽可能把呈现次数多的放在后面，于是，可采纳优先队列来保护每个数呈现的次数，每次取出呈现次数最多的数放到排列开端，留神，每取出一个数，该数的呈现次数就须要-1，当然，如果这个数与以后末尾数雷同，则以后必须换下一个数。
vector<int> rearrangeBarcodes(vector<int> &barcodes) { // 统计各数呈现次数 unordered_map<int, int> cnt; for (auto &e: barcodes)cnt[e]++; // 优先队列 priority_queue<pair<int, int>> q; for (const auto &[a, b]: cnt)q.emplace(b, a); // 每次取出队头元素 vector<int> res; while (q.size()) { auto [xs, x] = q.top(); q.pop(); // 排列开端不是x则往开端放x if (res.empty() || res.back() != x) { res.push_back(x); if (xs > 1)q.emplace(xs - 1, x); } // 如果开端是x则只能放其它数 else { // 题目保障有答案，所以到此处队列必然不为空 auto [ys, y] = q.top(); q.pop(); res.push_back(y); if (ys > 1)q.emplace(ys - 1, y); // 把x放回去 q.emplace(xs, x); } } return res;}工夫复杂度：O(nlog(n))
空间复杂度：O(n)
计数统计
通过后面剖析咱们发现，实际上，能够通过每隔一个地位放一个雷同数的操作来结构符合要求的排列。也即
- 第一个放数的地位是0，第二个放数的地位是2，以此类推，接着是4、6、...，当下标越界时，回到地位1，下一个放数的地位是3，再下一个是5，以此类推，接着是7、8、9...。
- 数一批一批地放，值相等的数形成一批，至于先放值等于几的那一批并没有要求。
- 特地的，当n为奇数且有元素x呈现次数为(n+1)/2时，地位0必须是x的，此时x占有全副偶数地位，不然放不下。
vector<int> rearrangeBarcodes(vector<int> &barcodes) { int l = barcodes.size(); if (l < 3)return barcodes; // 统计各数呈现次数 unordered_map<int, int> cnt; for (auto &e: barcodes)cnt[e]++; // 奇偶交替填充 vector<int> res(l); int even = 0, odd = 1, half = l / 2; for (auto &[x, xs]: cnt) { // 先填奇数地位 // xs<=half用于保障当n为奇数且元素x呈现次数为(n+1)/2时，x肯定能放在所有偶数地位上 while (xs > 0 && xs <= half && odd < l) res[odd] = x, xs--, odd += 2; // 再填偶数地位 while (xs > 0) res[even] = x, xs--, even += 2; } return res;}工夫复杂度：O(n)
空间复杂度：O(n)