【Day 90 】2023-05-14 - 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

[lp1506947671]

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;
    }
}

复杂度分析

设：元素个数为N，不重复元素个数为K

时间复杂度：O(NlogK)

空间复杂度：O(K)

[yingchehu]

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        cnt = collections.Counter(barcodes)
        index, n = 0, len(barcodes)
        ans = [0] * n
        for code, freq in cnt.most_common():
            for _ in range(freq):
                if index >= n:
                    index = 1
                ans[index] = code
                index += 2
        return ans

[RestlessBreeze]

code

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) 
    {
        unordered_map<int, int> count;
        for (int i = 0; i < barcodes.size(); i++)
            count[barcodes[i]]++;
        priority_queue<pair<int, int>> q;
        for (const auto &[x, cx] : count) 
        {
            q.push({cx, x});
        }
        vector<int> res;
        while (q.size()) 
        {
            auto [cx, x] = q.top();
            q.pop();
            if (res.empty() || res.back() != x) 
            {
                res.push_back(x);
                if (cx > 1) 
                {
                    q.push({cx - 1, x});
                }
            } 
            else 
            {
                if (q.size() < 1) 
                    return res;
                auto [cy, y] = q.top();
                q.pop();
                res.push_back(y);
                if (cy > 1)  
                {
                    q.push({cy - 1, y});
                }
                q.push({cx, x});
            }
        }
        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,cnt in sorted(((x,cnt) for x,cnt in Counter(barcodes).items()),key=lambda x:x[1],reverse=True):
            while cnt:
                cnt-=1
                if even<n:
                    ans[even]=x
                    even+=2
                else:
                    ans[odd]=x
                    odd+=2
        return ans

**复杂度分析**
- 时间复杂度：O(Nlogk)，其中 N 为重复字符数，k为不重复字符数。
- 空间复杂度：O(k)

[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).mostcommon(): for in range(v): res[i] = k i += 2 if i >= n: i = 1 return res

[enrilwang]

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

[snmyj]

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
      vector<int> ans;
      unordered_map<int,int> hashs;
      priority_queue<pair<int,int>, vector<pair<int,int>>,less<>> pq;
      for(auto x:barcodes) hashs[x]++;
      for(auto x:hashs) pq.push({x.second,x.first});
      while(!pq.empty()){
          int cur=pq.top().second;
          int cnt=pq.top().first;
          if(!ans.empty()&&cur==ans.back()){
              pair<int,int> temp=pq.top();
              pq.pop();
              int cur=pq.top().second;
              int cnt=pq.top().first;
              ans.push_back(cur);
             cnt--;
             pq.pop();
             if(cnt!=0)pq.push({cnt,cur});
             pq.push(temp);
             continue;

          }
          ans.push_back(cur);
          cnt--;
          pq.pop();
          if(cnt!=0)pq.push({cnt,cur});

      }
       return ans;
    }
}; 

[joemonkeylee]

function rearrangeBarcodes(barcodes: number[]): number[] {
  const mx = Math.max(...barcodes);
  const cnt = Array(mx + 1).fill(0);
  for (const x of barcodes) {
    ++cnt[x];
  }
  barcodes.sort((a, b) => (cnt[a] === cnt[b] ? a - b : cnt[b] - cnt[a]));
  const n = barcodes.length;
  const ans = Array(n);
  for (let k = 0, j = 0; k < 2; ++k) {
    for (let i = k; i < n; i += 2, ++j) {
      ans[i] = barcodes[j];
    }
  }
  return ans;
}

[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;
    }

[kangliqi1]

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;
}

}

[airwalkers]

class Solution {
    // 0 1 2 3 4 5 6
    // 1 1 1 1 2 2 2
    // o e
    // 2 1 2 1 2 1 1
    public int[] rearrangeBarcodes(int[] barcodes) {
        int[][] count = new int[10000 + 1][2];
        for (int i = 0; i < count.length; i++) {
            count[i][1] = i;
        }
        for (int code: barcodes) {
            count[code][0]++;
        }

        Arrays.sort(count, (o1, o2) -> o2[0] - o1[0]);

        int odd = 1, even = 0;
        int k = 0; // count index
        int[] res = new int[barcodes.length];
        while (even < barcodes.length || odd < barcodes.length) {
            int num = count[k][1];
            count[k][0]--;
            if (count[k][0] == 0) {
                k++;
            }
            if (even < barcodes.length) {
                res[even] = num;
                even += 2;
            } else {
                res[odd] = num;
                odd += 2;
            }
        }

        return res;
    }
}

[harperz24]

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        freq_counter = collections.Counter(barcodes)
        maxheap = [(-freq, code) for code, freq in freq_counter.items()]
        heapq.heapify(maxheap)

        res = []
        while len(maxheap) >= 2:
            freq1, code1 = heapq.heappop(maxheap)
            freq2, code2 = heapq.heappop(maxheap)

            res.append(code1)
            res.append(code2)

            freq1 += 1
            freq2 += 1

            if -freq1 > 0:
                heapq.heappush(maxheap, (freq1, code1))
            if -freq2 > 0:
                heapq.heappush(maxheap, (freq2, code2))

        while maxheap:
            res.append(heapq.heappop(maxheap)[1])

        return res

[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;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(N)

[JasonQiu]

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        result = [0] * len(barcodes)
        index = 0
        for barcode, freq in collections.Counter(barcodes).most_common():
            for _ in range(freq):
                if index >= len(barcodes):
                    index = 1
                result[index] = barcode
                index += 2
        return result

[NorthSeacoder]

/**
 * @param {number[]} barcodes
 * @return {number[]}
 */
var rearrangeBarcodes = function (barcodes) {
    const res = new Array(barcodes.length);
    const heap = new maxHeap();
    for (let code of barcodes) {
        heap.push(code)
    }
    for (let i = 0; i < barcodes.length; i += 2) {
        res[i] = heap.pop()
    }
    for (let i = 1; i < barcodes.length; i += 2) {
        res[i] = heap.pop()
    }
    return res
};
class maxHeap {
    constructor() {
        this.heap = [0];
        this.set = new Set();
    }
    //大->上
    shiftUp(i) {
        while (i >> 1 > 0) {
            const parentI = i >> 1;
            const parent = this.heap[parentI];
            const cur = this.heap[i];
            if (cur[1] > parent[1]) {
                [this.heap[parentI], this.heap[i]] = [cur, parent];
            }
            i = parentI;
        }
    }
    getMaxChild(i) {
        const len = this.heap.length - 1;
        if (2 * i + 1 > len) return 2 * i;
        const left = this.heap[2 * i][1];
        const right = this.heap[2 * i + 1][1];
        if (left > right) return 2 * i;
        return 2 * i + 1;
    }
    //小->下
    shiftDown(i) {
        const len = this.heap.length - 1;
        while (2 * i <= len) {
            const childI = this.getMaxChild(i);
            const child = this.heap[childI];
            const cur = this.heap[i];
            if (cur[1] < child[1]) {
                [this.heap[childI], this.heap[i]] = [cur, child];
            }
            i = childI;
        }
    }

    push(val) {
        if (!this.set.has(val)) {
            this.heap.push([val, 1]);
            this.shiftUp(this.heap.length - 1);
            this.set.add(val);
        } else {
            const index = this.heap.findIndex((item) => item[0] === val);
            this.heap[index][1]++;
            this.shiftUp(index);
        }
    }

    pop() {
        if (this.heap.length === 1) return;
        if (this.heap[1][1] > 1) {
            this.heap[1][1]--;
            return this.heap[1][0];
        } else {
            const last = this.heap.length - 1;
            const res = this.heap[1][0];
            this.heap[1] = this.heap[last];
            this.heap.pop();
            this.shiftDown(1);
            this.set.delete(res);
            return res;
        }
    }
}

[FireHaoSky]

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        count = Counter(barcodes)
        q = []
        for x, cx in count.items():
            heapq.heappush(q, (-cx, x))
        res = []
        while len(q) > 0:
            cx, x = heapq.heappop(q)
            if len(res) == 0 or res[-1] != x:
                res.append(x)
                if cx < -1:
                    heapq.heappush(q, (cx + 1, x))
            else:
                cy, y = heapq.heappop(q)
                res.append(y)
                if cy < -1:
                    heapq.heappush(q, (cy + 1, y))
                heapq.heappush(q, (cx, x))
        return res

[Lydia61]

1054. 距离相等的条形码

思路

条码计数排列

代码

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

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[Jetery]

class Solution {
public:
    int last;
    void fill(vector<int> &v, int k) {
        if (last >= v.size()) last = 1;
        v[last] = k;
        last += 2;
    }

    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int, int> mp;
        int key = 0, val = 0;
        for (int x : barcodes) {
            mp[x]++;
            if (val < mp[x]) {
                key = x;
                val = mp[x];
            }
        }

        int n = barcodes.size();
        last = val * 2;

        vector<int> ans(n);
        for (int i = 0; i < val; i++) 
            ans[i * 2] = key;

        for (auto &[k, v] : mp) {
            if (k == key) continue;
            for (int i = 0; i < v; i++) 
                fill(ans, k);
        }
        return ans;
    }
};

[kofzhang]

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        data = []
        for i, j in Counter(barcodes).most_common():
            data += [i] * j
        l = len(data)
        data[::2],data[1::2] = data[:(l+1)//2],data[(l+1)//2:]        
        return data