1054. 距离相等的条形码#

1
在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。
2

3
请你重新排列这些条形码，使其中两个相邻的条形码 不能相等。
4

5
你可以返回任何满足该要求的答案，此题保证存在答案。
6

7

8

9
示例 1：
10

11
输入：[1,1,1,2,2,2]
12
输出：[2,1,2,1,2,1]
13
示例 2：
14

15
输入：[1,1,1,1,2,2,3,3]
16
输出：[1,3,1,3,2,1,2,1]
17

18

19
提示：
20

21
1 <= barcodes.length <= 10000
22
1 <= barcodes[i] <= 10000

1
class Solution {
2
public:
3
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
4
        int n = barcodes.size();
5
        unordered_map<int, int> up;
6
        for(int i : barcodes) up[i]++;
7
        vector<pair<int,int>> ans;
8
        for(auto [x, fx] : up) ans.push_back(pair<int, int>{x, fx});
9

10
        sort(ans.begin(), ans.end(),
11
        [&](const pair<int, int> &a, const pair<int, int> &b)
12
        {
13
            return a.second > b.second;
14
        });
15

16
        vector<int> res(n);
17
        int m = 0;
18
        for(auto [x, fx] : ans)
19
        {
20
            for (int i = 0 ; i < fx; i++)
21
            {
22
                if (m >= n) m = 1;
23
                res[m] = x;
24
                m += 2;
25
            }
26
        }
27
        return res;
28
    }
29
};