【Day 90 】2024-07-06 - 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

[zhiyuanpeng]

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        count = collections.Counter(barcodes)
        q = [(-v, k) for k, v in count.items()]
        heapq.heapify(q)
        ans = []
        while q:
            v1, k1 = heapq.heappop(q)
            ans.append(k1)
            if q:
                v2, k2 = heapq.heappop(q)
                ans.append(k2)
                if v2 + 1 != 0:
                    heapq.heappush(q, (v2+1, k2))
            if v1 + 1 != 0:
                heapq.heappush(q, (v1+1, k1))
        return ans

[CathyShang]

堆+贪心：取数量最多的前两个元素进行排列

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counter = Counter(barcodes)
        h = [(-v,k) for k,v in counter.items()]
        heapify(h)
        ans = []
        while h:
            v, k = heappop(h)
            v = -v
            ans.append(k)
            if h:
                v2, k2 = heappop(h)
                v2 = -v2
                ans.append(k2)
                if v2>1:
                    heappush(h, (-(v2-1),k2))
            if v>1:
                heappush(h, (-(v-1),k))
        return ans

[Dtjk]

class Solution { public: vector rearrangeBarcodes(vector& 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; } };