1054. Distant Barcodes

1054. Distant Barcodes (Medium)

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

 

Related Topics:
Heap, Sort

Solution 1. Greedy + Heap

// OJ: https://leetcode.com/problems/distant-barcodes/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& A) {
        unordered_map<int, int> cnt;
        for (int n : A) cnt[n]++;
        auto cmp = [&](int a, int b) { return cnt[a] < cnt[b]; };
        priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
        for (auto &p : cnt) q.push(p.first);
        int prev = 0;
        vector<int> ans;
        while (q.size()) {
            int n = q.top();
            q.pop();
            ans.push_back(n);
            if (prev) q.push(prev);
            if (--cnt[n]) prev = n;
            else prev = 0;
        }
        return ans;
    }
};

Solution 2. Interleaving Placement

// OJ: https://leetcode.com/problems/distant-barcodes/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& A) {
        unordered_map<int, int> cnt;
        set<pair<int, int>> s;
        for (int n : A) cnt[n]++;
        for (auto &p : cnt) s.emplace(p.second, p.first);
        int j = 0, N = A.size();
        vector<int> ans(N);
        for (auto it = s.rbegin(); it != s.rend(); ++it) {
            for (int c = 0; c < it->first; ++c, j += 2) {
                if (j >= N) j = 1;
                ans[j] = it->second;
            }
        }
        return ans;
    }
};

Solution 3.

Just fill the most frequent number first. The others can be filled irrespective of their frequency.

// OJ: https://leetcode.com/problems/distant-barcodes/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& A) {
        short cnt[10001] = {}, maxCnt = 0, num = 0, j = 0;
        for (int n : A) {
            maxCnt = max(maxCnt, ++cnt[n]);
            if (maxCnt == cnt[n]) num = n;
        }
        for (int i = 0; i <= 10000; ++i) {
            int n = i ? i : num;
            while (cnt[n]-- > 0) {
                A[j] = n;
                j = (j + 2) % A.size();
                if (j == 0) j = 1;
            }
        }
        return A;
    }
};