1054. Distant Barcodes

In a warehouse, there is a row of barcodes, where the ith barcode is barcodes[i].

Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.

Example 1:

Input: barcodes = [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]

Example 2:

Input: barcodes = [1,1,1,1,2,2,3,3]
Output: [1,3,1,3,1,2,1,2]

Constraints:

  • 1 <= barcodes.length <= 10000
  • 1 <= barcodes[i] <= 10000

这道题说在一个仓库,有一排条形码,这里用数字表示,现在让给数字重新排序,使得相邻的数字不相同,并且说了一定会有合理的答案。意思就是说最多的重复个数不会超过数组长度的一半,否则一定会有相邻的重复数字。那么来分析一下题目,既然是为了避免重复数字被排在相邻的位置,肯定是要优先关注出现次数多的数字,因为它们更有可能出现在相邻的位置。这道题是可以用贪婪算法来做的,每次取出出现次数最多的两个数字,将其先排列起来,然后再取下一对出现次数最多的两个数字,以此类推直至排完整个数组。这里为了快速知道出现次数最多的数字,可以使用优先队列来做,里面放一个 pair 对儿,由频率和数字组成,这样优先队列就可以根据频率由高到低来自动排序了。统计频率的话就使用一个 HashMap,然后将频率和数字组成的 pair 对儿加入优先队列。进行 while 循环,条件是队列中的 pair 对儿至少两个,这样才能每次取出两个,将其加入结果 res 中,然后其频率分别减1,只要没减到0,就都加回优先队列中。最后可能队列还有一个剩余,有的话将数字加入结果 res 中即可,参见代码如下:

解法一:

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        vector<int> res;
        priority_queue<pair<int, int>> pq;
        unordered_map<int, int> numCnt;
        for (int num : barcodes) ++numCnt[num];
        for (auto &a : numCnt) {
            pq.push({a.second, a.first});
        }
        while (pq.size() > 1) {
            auto a = pq.top(); pq.pop();
            auto b = pq.top(); pq.pop();
            res.push_back(a.second);
            res.push_back(b.second);
            if (--a.first > 0) pq.push(a);
            if (--b.first > 0) pq.push(b);
        }
        if (!pq.empty()) res.push_back(pq.top().second);
        return res;
    }
};

论坛上的高分解法貌似没有用到优先队列,不过整个思路还是大体相同的,还是用 HashMap 来统计频率,这里将组成的频率和数字的 pair 对儿放到一个数组中,然后给数组按照从大到小的顺序来排列。接下里就要填充 res 数组了,方法是先填偶数坐标的位置,将频率最大的数字分别填进去,当偶数坐标填完了之后,再填奇数坐标的位置,这样保证不会有相连的重复数字。使用一个变量 pos,表示当前要填的坐标,初始化为0,之后来遍历这个频率和数字的 pair 对儿,从高到低,先填充所有偶数,若 pos 大于数组长度了,则切换为填充奇数即可,参见代码如下:

解法二:

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        int n = barcodes.size(), pos = 0;
        vector<int> res(n);
        vector<pair<int, int>> vec;
        unordered_map<int, int> numCnt;
        for (int num : barcodes) ++numCnt[num];
        for (auto &a : numCnt) {
            vec.push_back({a.second, a.first});
        }
        sort(vec.rbegin(), vec.rend());
        for (auto &a : vec) {
            for (int i = 0; i < a.first; ++i, pos += 2) {
                if (pos >= n) pos = 1;
                res[pos] = a.second;
            }
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1054

参考资料:

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

https://leetcode.com/problems/distant-barcodes/discuss/299371/C%2B%2B-with-picture-O(N)

https://leetcode.com/problems/distant-barcodes/discuss/299225/JavaPython-Set-Odd-Position-and-Even-Position

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation