[Leetcode 1054] Distant Barcodes

原题说明

In a warehouse, there is a row of barcodes, where the i-th 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: [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]

Example 2:

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

 

Note:

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

解题思路

题目要求将给定的数组重新排列，排列后的数组，相同的数不再相邻，并且保证一定存在解。

这题因为一定存在解，我们可以用贪心的算法重排数组。先计算每个数据出现次的频率。每次取出频率最高的两个数据，比较哪个可以放入当前新的数组中，并更新数据出现的频率。直到安排完所有的数据。

因为每次都要取出频率最高的两个数据，所以我们选择使用优先队列heap来储存数据。

示例代码 (cpp)

class Solution {
private:
struct cmp {
    bool operator() (const pair<int,int>& p1, const pair<int,int>& p2) {
        return p1.second < p2.second;
    }
};
    
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> pq;
        unordered_map<int,int> dict;
        for (const auto& barcode : barcodes) {
            dict[barcode]++;
        }
        for (const auto& ele : dict) {
            pq.push({ele.first, ele.second});
        }
        vector<int> ans;
        while (!pq.empty()) {
            auto p1 = pq.top();
            pq.pop();
            if (ans.size() == 0 || ans.back() != p1.first) {
                ans.emplace_back(p1.first);
                if (p1.second > 1) {
                    pq.push({p1.first, p1.second - 1});
                }
            }
            else {
                assert(!pq.empty());
                auto p2 = pq.top();
                pq.pop();
                ans.emplace_back(p2.first);
                if (p2.second > 1) {
                    pq.push({p2.first, p2.second - 1});
                }
                pq.push(p1);
            }
        }
        return ans;
    }
};

示例代码 (java)

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> cnt = new HashMap();
        for (int i : barcodes) cnt.put(i, cnt.getOrDefault(i, 0) + 1);

        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(cnt.entrySet());
        Collections.sort(list, Map.Entry.<Integer, Integer>comparingByValue().reversed());
        int l = barcodes.length, i = 0;
        int[] res = new int[l];
        for (Map.Entry<Integer, Integer> e : list) {
            int time = e.getValue();
            while (time-- > 0) {
                res[i] = e.getKey();
                i += 2;
                if (i >= barcodes.length) i = 1;
            }
        }
        return res;
    }
}

示例代码 (python)

class Solution:
    def rearrangeBarcodes(self, packages):
        i, n = 0, len(packages)
        res = [0] * n
        for k, v in collections.Counter(packages).most_common():
            for _ in range(v):
                res[i] = k
                i += 2
                if i >= n: i = 1
        return res

复杂度分析

时间复杂度: O(nlogn)
空间复杂度: O(1)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！