题目地址：

https://leetcode.com/problems/distant-barcodes/description/

给定一个长nnn数组AAA，要求重排之，使得相邻数字不同。题目保证答案存在。

直觉上，只需按频率从大到小排序，然后依次排在0,2,4,...0,2,4,...0,2,4,...这些位置，越界了则再从1,3,5...1,3,5...1,3,5...排即可。可以证明这样的方法一定成立，如果存在某两个相邻的位置数字相等，那么这个数字一定出现了⌈n2⌉\lceil \frac{n}{2}\rceil⌈2n​⌉次（或者更多，但是更多的话就无解了），而这样的数只能有一个，并且一定是第一轮已经排好了，就矛盾了。代码如下：

class Solution {public:using PII = pair;vector rearrangeBarcodes(vector &bs) {unordered_map mp;for (int x : bs) mp[x]++;vector v;for (auto &[k, c] : mp) v.push_back({c, k});sort(v.begin(), v.end(), greater());int idx = 0;for (auto &p : v)for (int i = 0; i < p.first; i++) {bs[idx] = p.second;idx += 2;if (idx >= bs.size()) idx = 1;}return bs;}
};

时间复杂度O(nlog⁡n)O(n\log n)O(nlogn)，空间O(n)O(n)O(n)。