【每日一题】距离相等的条形码

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 

优先队列

直观上来看，我们应该尽可能把出现次数多的放在前面，于是，可采用优先队列来维护每个数出现的次数，每次取出出现次数最多的数放到排列末尾，注意，每取出一个数，该数的出现次数就需要-1，当然，如果这个数与当前末尾数相同，则当前必须换下一个数。

vector rearrangeBarcodes(vector &barcodes) {
    // 统计各数出现次数
    unordered_map cnt;
    for (auto &e: barcodes)cnt[e]++;
    // 优先队列
    priority_queue> q;
    for (const auto &[a, b]: cnt)q.emplace(b, a);
    // 每次取出队头元素
    vector 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 rearrangeBarcodes(vector &barcodes) {
    int l = barcodes.size();
    if (l  cnt;
    for (auto &e: barcodes)cnt[e]++;
    // 奇偶交替填充
    vector res(l);
    int even = 0, odd = 1, half = l / 2;
    for (auto &[x, xs]: cnt) {
        // 先填奇数位置
        // xs 0 && xs  0)
            res[even] = x, xs--, even += 2;
    }
    return res;
}

时间复杂度：O(n)

空间复杂度：O(n)

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net