Description

Submission

constexpr int maxn = 10001;
class Solution {
    int cnts[maxn];
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        int n = barcodes.size();
        vector<int> rets(n);

        for(auto x: barcodes) {
            ++cnts[x];
        }

        int maxi = 0;
        for(int i = 1; i < maxn; ++i) {
            if(cnts[maxi] < cnts[i]) maxi = i;
        }

        int ptr = maxi;

        for(int i = 0; i < n; i += 2) {
            while(!cnts[ptr]) ptr = (ptr + 1) % maxn;
            rets[i] = ptr;
            --cnts[ptr];
        }


        for(int i = 1; i < n; i += 2) {
            while(!cnts[ptr]) ptr = (ptr + 1) % maxn;
            rets[i] = ptr;
            --cnts[ptr];
        }

        return rets;
    }
};