【Day 90 】2023-09-07 - 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

[yetfan]

代码

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        length = len(barcodes)
        if length < 2:
            return barcodes

        counts = {}
        max_count = 0
        for b in barcodes:
            counts[b] = counts.get(b, 0) + 1
            max_count = max(max_count, counts[b])

        evenIndex = 0
        oddIndex = 1
        half_length = length // 2
        res = [0] * length
        for x, count in counts.items():
            while count > 0 and count <= half_length and oddIndex < length:
                res[oddIndex] = x
                count -= 1
                oddIndex += 2
            while count > 0:
                res[evenIndex] = x
                count -= 1
                evenIndex += 2
        return res

[Diana21170648]

思路

堆，分奇数和偶数，按频率的降序排序

代码

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        n=len(barcodes)
        ans=[0]*n
        even,odd=0,1
        for x,count in sorted(((x,count) for x,count in Counter(barcodes).items()),key=lambda x:x[1],reverse=True):
            while count:
                count-=1
                if even<n:
                    ans[even]=x
                    even+=2
                else:
                    ans[odd]=x
                    odd+=2
        return ans

复杂度分析

• 时间复杂度：O(NlogK)，其中 N 为元素个数，K为不重复元素的个数。
• 空间复杂度：O(K),K为不重复元素的个数。

[Fuku-L]

代码

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        int len = barcodes.length;
        if(len < 2){
            return barcodes;
        }
        Map<Integer, Integer> counts = new HashMap<>();
        int maxCnt = 0;
        for(int b: barcodes){
            counts.put(b, counts.getOrDefault(b, 0)+1);
            maxCnt = maxCnt > counts.get(b) ? maxCnt:counts.get(b);
        }
        int evenIdx = 0, oddIdx = 1;
        int halfLen = len / 2;
        int[] res = new int[len];
        for(Map.Entry<Integer, Integer> entry: counts.entrySet()){
            int x = entry.getKey();
            int cnt = entry.getValue();
            while(cnt > 0 && cnt <= halfLen && oddIdx < len){
                res[oddIdx] = x;
                cnt--;
                oddIdx += 2;
            }
            while(cnt > 0){
                res[evenIdx] = x;
                cnt--;
                evenIdx += 2;
            }
        }
        return res;
    }
}

[Alexno1no2]

# 计数 + 排序
# 1、先用哈希表或数组 cnt 统计数组 barcodes 中各个数出现的次数，然后将 barcodes 中的数按照它们在 cnt 中出现的次数从大到小排序，如果出现次数相同，那么就按照数的大小从小到大排序（确保相同的数相邻）。

# 2、创建一个长度为 n 的答案数组 ans ，然后遍历排好序的 barcodes ，将元素依次填入答案数组的 0,2,4,⋯ 等偶数下标位置，然后将剩余元素依次填入答案数组的 1,3,5,⋯ 等奇数下标位置即可。

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        cnt = Counter(barcodes)
        barcodes.sort(key=lambda x: (-cnt[x], x))
        n = len(barcodes)
        ans = [0] * len(barcodes)
        ans[::2] = barcodes[: (n + 1) // 2]
        ans[1::2] = barcodes[(n + 1) // 2:]
        return ans