关于算法:每日一题距离相等的条形码

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 <= 10000
1 <= 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)