本文涉及知识点
LeetCode1054. 距离相等的条形码
在一个仓库里，有一排条形码，其中第 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
贪心
性质一：一排条型码长度n，出现次数最多的条形码出现次数<= n/2。则限制队首不为指定字符也可以让相邻不相等。
性质二：一排条型码长度n，n位奇数。出现最多的条形码出现n/2+1次。如果队首可以为此条形码，则可以让相邻不相等。
下面用数学归纳法来证明。
n为1成立：{a}
n为2成立：{a,b},{b,a}
n为3成立：{a,b,a} {a,b,c}{a,c,b}
从小到大证明n = 4 To ∞ \infty ∞
n为偶数：
如果存在两个众数为n/2，将任意众数放到队首，余下的符合性质二。
否则，将任意众数放到队首，余下的符合性质一。
n为奇数：
如果众数为n/2+1，则只有一个众数。否则两个众数的数量为n+1，与n个数矛盾。
将众数放到队首，余下的符合性质一。
从上面的证明过程得知：如果有解，则将众数放到最前面，一定存在解。
pre记录上次操作的条形码，避免相邻相同。
代码
核心代码
class Solution {public:vector<int> rearrangeBarcodes(vector<int>& barcodes) {const int iMax = *max_element(barcodes.begin(), barcodes.end());vector<int> cnt(iMax + 1);for (const auto& n : barcodes) {cnt[n]++;}priority_queue<pair<int, int>> heap;for (int i = 0; i <= iMax; i++) {heap.emplace(cnt[i], i);}vector<int> ans;pair<int, int> pre = { -1,-1 };while (heap.top().first > 0) { auto cur = heap.top();cur.first--;ans.emplace_back(heap.top().second);heap.pop(); heap.emplace(pre);pre = cur;}return ans;}};
单元测试
void Check(const vector<int>& res) {for (int i = 1; i < res.size(); i++){Assert::IsTrue(res[i - 1]!= res[i]);}}vector<int> barcodes;TEST_METHOD(TestMethod11){barcodes = { 1, 1, 1, 2, 2, 2 };auto res = Solution().rearrangeBarcodes(barcodes);Check(res);AssertSort(res, barcodes);}TEST_METHOD(TestMethod12){barcodes = { 1,1,1,1,2,2,3,3 };auto res = Solution().rearrangeBarcodes(barcodes);Check(res);AssertSort(res, barcodes);}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
