【Day 90 】2023-01-29 - 1054. 距离相等的条形码

[azl397985856]

1054. 距离相等的条形码

入选理由

暂无

题目地址

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

前置知识

• 堆
• 贪心

题目描述

在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。

请你重新排列这些条形码，使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案，此题保证存在答案。

 

示例 1：

输入：[1,1,1,2,2,2]
输出：[2,1,2,1,2,1]
示例 2：

输入：[1,1,1,1,2,2,3,3]
输出：[1,3,1,3,2,1,2,1]
 

提示：

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

[Ryanbaiyansong]

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        n = len(barcodes)
        cnt = {}
        for barcode in barcodes:
            cnt[barcode] = cnt.get(barcode, 0) + 1
        items = [(-val, key) for key, val in cnt.items()]
        heapq.heapify(items)

        cur = []
        while items:
            val, key = heapq.heappop(items)
            cur += [key] * (-val)
        j = 0    
        res = [0] * n
        for i in range(0, n, 2):
            res[i] = cur[j]
            j += 1
        for i in range(1, n, 2):
            res[i] = cur[j]
            j += 1
        return res

[snmyj]

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        int repeatsign;
        sort(barcodes.begin(),barcodes.end());
        vector<int> repeat,temp;
        for(int i=0;i<barcodes.size()-1;i++){
            if(barcodes[i+1]==barcodes[i]){ 
                repeat.push_back(barcodes[i+1]);
                barcodes.erase(barcodes.begin()+i+1);
                i--;
            }
        }
        temp=repeat;
        while(temp.size()!=0){
                if(temp.size()==1) {
                     barcodes.push_back(temp[0]);
                     return barcodes;
                }
                for(int i=0;i<temp.size();i++){
                    if(temp[i]==repeatsign) continue;
                    if(temp[i+1]!=temp[i]) {
                        barcodes.push_back(temp[i]);
                        temp.erase(temp.begin()+i);
                        i--;
                        continue;
                    }
                    else {
                         repeatsign=temp[i];
                         barcodes.push_back(temp[i]);
                         temp.erase(temp.begin()+i);
                         
                    }
                  
                }
        }
        return barcodes;
    }
};

[Abby-xu]

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

[whoam-challenge]

class Solution:
def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
n = len(barcodes)
cnt = {}
for barcode in barcodes:
cnt[barcode] = cnt.get(barcode, 0) + 1
items = sorted([(-val, key) for key, val in cnt.items()])

    cur = []
    for val, key in items:
        cur += [key] * (-val)
        
    j = 0    
    res = [0] * n
    for i in range(0, n, 2):
        res[i] = cur[j]
        j += 1
    for i in range(1, n, 2):
        res[i] = cur[j]
        j += 1
    return res

[bookyue]

public int[] rearrangeBarcodes(int[] barcodes) {
    if (barcodes == null || barcodes.length <= 1) return barcodes;

    int[] cnt = new int[10_001];
    for (int barcode : barcodes)
        cnt[barcode]++;

    var maxHeap = new PriorityQueue<Integer>(Comparator.comparingInt(i -> -cnt[i]));
    for (int i = 0; i < cnt.length; i++) {
        if (cnt[i] == 0) continue;

        maxHeap.offer(i);
    }

    int n = barcodes.length;
    int[] ans = new int[n];
    int i = 0;
    while (maxHeap.size() >= 2) {
        var k1 = maxHeap.poll();
        var k2 = maxHeap.poll();
        cnt[k1]--;
        cnt[k2]--;

        ans[i] = k1;
        ans[i + 1] = k2;
        i += 2;
        if (cnt[k1] > 0) maxHeap.offer(k1);
        if (cnt[k2] > 0) maxHeap.offer(k2);
    }

    if (!maxHeap.isEmpty()) ans[i] = maxHeap.poll();

    return ans;
}

[klspta]

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        int n = barcodes.length;
        int[] cnt = new int[10001];
        for(int barcode : barcodes){
            cnt[barcode]++;
        }

        List<Integer> items = new ArrayList<>();
        for(int i = 1; i < cnt.length; i++){
            if(cnt[i] != 0){
               items.add(i); 
            }
        }
        items.sort((o1, o2) -> cnt[o2] - cnt[o1]);

        int[] cur = new int[n];
        int j = 0;
        for(int item : items){
            for(int i = 0; i < cnt[item]; i++){
                cur[j++] = item;
            }
        }

        int[] res = new int[n];
        j = 0; 
        for(int i = 0; i < n; i += 2){
            res[i] = cur[j++];
        }
        for(int i = 1; i < n; i += 2){
            res[i] = cur[j++];
        }
        return res;
    }
}

[RestlessBreeze]

code

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& b) {
        priority_queue<pair<int, int>> q;
        unordered_map<int,int> mp;
        for(auto x: b){
            mp[x]++;
        }
        for(const auto &[k, v]: mp) {
            q.push({v, k});
        }
        vector<int> res;

        while(q.size()) {
            auto [v, k] = q.top(); q.pop();
            if(res.empty() || res.back() != k) {
                res.push_back(k);
                if(--v) q.push({v, k});
            }else{
                if(q.size() < 1) return res;
                auto [y, x] = q.top(); q.pop();
                res.push_back(x);
                if(--y) q.push({y, x});
                q.push({v, k});
            }
        }
        return res;
    }
};

[paopaohua]

class Solution {

    public int[] rearrangeBarcodes(int[] barcodes) {

        Map<Integer, Integer> counter = new HashMap<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> (counter.get(y) - counter.get(x)));

        for (int num : barcodes)
            counter.put(num, counter.getOrDefault(num, 0) + 1);

        for (int num : counter.keySet())
            pq.offer(num);

        int idx = 0;

        while (pq.size() > 1) {

            int first = pq.poll(), second = pq.poll();

            barcodes[idx++] = first;
            barcodes[idx++] = second;

            counter.put(first, counter.get(first) - 1);
            counter.put(second, counter.get(second) - 1);

            if (counter.get(first) > 0)
                pq.offer(first);
            if (counter.get(second) > 0)
                pq.offer(second);
        }

        if (pq.size() > 0)
            barcodes[idx++] = pq.poll();

        return barcodes;
    }
}

[tiandao043]

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int,int> m;
        priority_queue<pair<int,int>> pq;
        for(int b:barcodes){
            m[b]++;
        }
        for(auto [k,v]:m){
            pq.push({v,k});
        }
        int n=barcodes.size();
        vector<int> ans(n,0);
        int i=0;
        while(pq.size()>1){
            int f=pq.top().second;pq.pop();
            int s=pq.top().second;pq.pop();
            ans[i++]=f;
            ans[i++]=s;
            m[f]--;
            m[s]--;
            if(m[f]>0){
                pq.push({m[f],f});
            }
            if(m[s]>0)pq.push({m[s],s});
            // ans[i]=;
            // pq.pop();
            // i+=2;
            // if(i>=n)i=1;
        }
        if(pq.size()>0)ans[i++]=pq.top().second;

        return ans;
    }
};

设：元素个数为N，不重复元素个数为K
时间复杂度：
O(NlogK)
空间复杂度：
O(K)

[Elsa-zhang]

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        ans = []
        n = len(barcodes)
        while len(ans)!=n:
            if len(barcodes)==1:
                ans.append(barcodes[0])
                break
            record = {}
            for num in barcodes:
                record[num] = record.get(num, 0)+1
            record = sorted(record.items(), key=lambda x: x[1], reverse=True)
            for i in range(2):
                ans.append(record[i][0])
                barcodes.remove(record[i][0])
        return ans

[mayloveless]

思路

用堆排序出现的次数大小，岔开输出，先放次数多的。2个一组即可岔开。

代码

/**
 * @param {number[]} barcodes
 * @return {number[]}
 */
var rearrangeBarcodes = function(barcodes) {
    const map = {};
    for(let i=0;i<barcodes.length;i++) {
        map[barcodes[i]] = (map[barcodes[i]] ?? 0) + 1;
    }

    const maxQ = new MaxPriorityQueue({
        priority: node => node.count
    });
    for(let key in map) {
       maxQ.enqueue({
           num: key,
           count: map[key],
       });
    }
    
    const res = [];
    while(maxQ.size()>1) {
        const first = maxQ.dequeue().element;
        const second = maxQ.dequeue().element;
        res.push(first.num);
        res.push(second.num)
        map[first.num] = first.count-1;
        map[second.num] = second.count-1;
           
        // 先放second，避免count相同，输出顺序相反
        if (map[second.num] > 0) {
            maxQ.enqueue({
                num: second.num,
                count: map[second.num],
            });
        }
        if (map[first.num] > 0) {
            maxQ.enqueue({
                num: first.num,
                count: map[first.num],
            });
        }
    }
    if (maxQ.size() > 0) {
        res.push(maxQ.dequeue().element.num)
    }
  
    return res;
};

复杂度

时间O(n*logk)
空间：O（k）

[Jetery]

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        int size = barcodes.size();
        unordered_map<int,int> map;
        for(auto b : barcodes)
            ++map[b];
        vector<pair<int,int>> slt;
        for(auto it = map.begin(); it != map.end(); ++it) 
            slt.push_back({it -> first, it -> second});
        sort(slt.begin(), slt.end(), [](pair<int,int> lhs, pair<int,int> rhs) {
            return lhs.second > rhs.second;
        });
        int index = 0, res_index = 0;
        while(index < slt.size()) 
            barcodes[res_index] = slt[index].first;
            res_index += 2;
            --slt[index].second;
            if(!slt[index].second) ++index;
            if(res_index >= size) res_index = 1;
        }
        return barcodes;
    }
};