【Day 90 】2022-03-11 - 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

[rzhao010]

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        if (barcodes.length < 2 || barcodes == null) return barcodes;
        int[] counts = new int[10001], res = new int[barcodes.length];
        for (int barcod: barcodes) {
            counts[barcod]++;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> counts[b] - counts[a]);
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] != 0) {
                queue.offer(i);
            }
        }
        int id = 0;
        while (queue.size() > 1) {
            int a = queue.poll();
            int b = queue.poll();
            res[id++] = a;
            res[id++] = b;
            if (counts[a] > 1) {
                counts[a]--;
                queue.offer(a);
            }
            if (counts[b] > 1) {
                counts[b]--;
                queue.offer(b);
            }
        }
        if (!queue.isEmpty()) {
            res[id] = queue.poll();
        }
        return res;
    }
}

[zhangzz2015]

思路

• 核心思路找到出现最多次数的num，首先排该num，后面的num的顺序没关系。具体实现方法采用multimap对num count排序，时间复杂度为 O(nlogn)，可进一步优化到O(n)，空间复杂度为 O(n)。

关键点

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int,int> countNum; 
        for(int i=0; i< barcodes.size(); i++)
            countNum[barcodes[i]]++; 
        multimap<int,int> sortNum; 
        for(auto it = countNum.begin(); it!=countNum.end(); it++)
        {
            sortNum.insert(make_pair((*it).second, (*it).first )); 
        }
        vector<int> ret(barcodes.size()); 
        int start =0;         
        for(auto it = sortNum.rbegin(); it!=sortNum.rend(); it++)
        {
            for(int i=0; i< (*it).first; i++)
            {
                ret[start] = (*it).second; 
                start=start+2; 
                if(start>=barcodes.size())
                    start=1; 
            }
        }
        return ret; 

    }
};

[Tesla-1i]

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        if (barcodes.length < 2 || barcodes == null) return barcodes;
        int[] counts = new int[10001], res = new int[barcodes.length];
        for (int barcod: barcodes) {
            counts[barcod]++;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> counts[b] - counts[a]);
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] != 0) {
                queue.offer(i);
            }
        }
        int id = 0;
        while (queue.size() > 1) {
            int a = queue.poll();
            int b = queue.poll();
            res[id++] = a;
            res[id++] = b;
            if (counts[a] > 1) {
                counts[a]--;
                queue.offer(a);
            }
            if (counts[b] > 1) {
                counts[b]--;
                queue.offer(b);
            }
        }
        if (!queue.isEmpty()) {
            res[id] = queue.poll();
        }
        return res;
    }
}

[xuhzyy]

class Solution(object):
    def rearrangeBarcodes(self, barcodes):
        """
        :type barcodes: List[int]
        :rtype: List[int]
        """
        n = len(barcodes)
        cnt = {}
        for barcode in barcodes:
            cnt[barcode] = cnt.get(barcode, 0) + 1
        h = sorted([(-val, key) for key, val in cnt.items()])
        cur = []
        for val, key in h:
            cur += [key] * (-val)
        res = [0] * n
        j = 0
        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

[1149004121]

1054. 距离相等的条形码

思路

堆

代码

var rearrangeBarcodes = function(barcodes) {
    let map = new Map();
    let heap = new MaxPriorityQueue();
    let res = [];
    for(let b of barcodes){
        map.set(b, (map.get(b) || 0) + 1);
    };
    for(let [key, value] of map.entries()){
        heap.enqueue(key, value);
    };
    let idx = 0;
    while(heap.size() > 1){
        let first = heap.dequeue();
        let second = heap.dequeue();
        res[idx++] = first["element"];
        res[idx++] = second["element"];
        if(second["priority"] - 1 > 0) heap.enqueue(second["element"], second["priority"] - 1);
        if(first["priority"] - 1 > 0) heap.enqueue(first["element"], first["priority"] - 1);
    };
    if(heap.size() > 0){
        let first = heap.dequeue();
        res[idx++] = first["element"];
    }
    return res;
};

复杂度分析

• 时间复杂度：O( N*logN) 。
• 空间复杂度：O(N) 。

[tongxw]

思路

贪心 + 堆排序，每次从堆里取出剩余次数追多的两数字，填写到结果数组里。

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int bc : barcodes) {
            count.put(bc, count.getOrDefault(bc, 0) + 1);
        }

        int[] res = new  int[barcodes.length];
        PriorityQueue<Integer> q = new PriorityQueue<>((code1, code2) -> count.get(code2) - count.get(code1));
        for (int bc: count.keySet()) {
            q.offer(bc);
        }

        int idx = 0;
        while (q.size() >= 2) {
            int num1 = q.poll();
            int num2 = q.poll();
            res[idx++] = num1;
            res[idx++] = num2;
            if (count.get(num1) > 1) {
                count.put(num1, count.get(num1) - 1);
                q.offer(num1);
            }
            if (count.get(num2) > 1) {
                count.put(num2, count.get(num2) - 1);
                q.offer(num2);
            }
        }

        if (!q.isEmpty()) {
            res[idx++] = q.poll();
        }

        return res;
    }
}

TC: O(n) + O(N logk) k为不同barcode的个数。 SC: O(k)

[LannyX]

思路

PQ

代码

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> mp = new HashMap<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> (mp.get(b) - mp.get(a)));

        for(int n : barcodes){
            mp.put(n, mp.getOrDefault(n, 0) + 1);
        }
        for(int num : mp.keySet()){
            pq.offer(num);
        }

        int idx = 0;

        while(pq.size() > 1){
            int fir = pq.poll(), sec = pq.poll();
            barcodes[idx++] = fir;
            barcodes[idx++] = sec;

            mp.put(fir, mp.get(fir) - 1);
            mp.put(sec, mp.get(sec) - 1);

            if (mp.get(fir) > 0){
                pq.offer(fir);
            }

            if (mp.get(sec) > 0){
                pq.offer(sec);
            }   
        }

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

        return barcodes;
    }
}

[cszys888]

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        from collections import Counter
        count = Counter(barcodes)
        distinct = sorted(count.keys(), key = lambda x: count[x], reverse = True)
        n = len(barcodes)
        cur = []
        for key in distinct:
            cur += [key]*count[key]
        j = 0
        result = [0]*n
        for i in range(0,n,2):
            result[i] = cur[j]
            j += 1
        for i in range(1, n, 2):
            result[i] = cur[j]
            j += 1
        return result

time complexity: O(n + klogk) space complexity: O(n)

[dahaiyidi]

Problem

[1054. 距离相等的条形码](https://leetcode-cn.com/problems/distant-barcodes/)

++

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

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

示例 1：

输入：barcodes = [1,1,1,2,2,2]
输出：[2,1,2,1,2,1]

示例 2：

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

---

Note

• 见程序

---

Complexity

• 时间O：
• 空间O：n

---

Python

C++

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        vector<int> res(barcodes.size(), INT_MIN);
        unordered_map<int, int> mp;
        priority_queue<pair<int, int>> pq;
        // 统计出现的次数
        for(auto& i: barcodes){
            mp[i] += 1;
        }

        // 根据出现次数加入最大堆，达到按照出现次数排序的目的
        for(auto& i: mp){
            pq.push({i.second, i.first}); // first 为数值， second为该数值出现的次数
        }

        // 从pq中按次序添加进入res中, 先填写偶数位（按照索引是偶数位），再按次序填写奇数位，则可以保证数值两两不同
        auto p = pq.top();
        pq.pop();

        // 填写偶数位
        for(int j = 0; j < res.size(); j += 2){
            res[j] = p.second;
            p.first--;
            // 如果当前数值的次数不够使用，则拿新的数值
            if(p.first == 0){
                p = pq.top();
                pq.pop();
            }
        }

        // 填写奇数位
        for(int j = 1; j < res.size(); j += 2){
            res[j] = p.second;
            p.first--;
            if(p.first == 0){
                p = pq.top();
                pq.pop();
            }
        }
        return res;
    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

[dahaiyidi]

Problem

[1054. 距离相等的条形码](https://leetcode-cn.com/problems/distant-barcodes/)

++

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

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

示例 1：

输入：barcodes = [1,1,1,2,2,2]
输出：[2,1,2,1,2,1]

示例 2：

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

---

Note

• 见程序

---

Complexity

• 时间O：n + klogk， n是barcodes.size(), k是不同数值的个数
• 空间O：n

---

Python

C++

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        vector<int> res(barcodes.size(), INT_MIN);
        unordered_map<int, int> mp;
        priority_queue<pair<int, int>> pq;
        // 统计出现的次数
        for(auto& i: barcodes){
            mp[i] += 1;
        }

        // 根据出现次数加入最大堆，达到按照出现次数排序的目的
        for(auto& i: mp){
            pq.push({i.second, i.first}); // first 为数值， second为该数值出现的次数
        }

        // 从pq中按次序添加进入res中, 先填写偶数位（按照索引是偶数位），再按次序填写奇数位，则可以保证数值两两不同
        auto p = pq.top();
        pq.pop();

        // 填写偶数位
        for(int j = 0; j < res.size(); j += 2){
            res[j] = p.second;
            p.first--;
            // 如果当前数值的次数不够使用，则拿新的数值
            if(p.first == 0){
                p = pq.top();
                pq.pop();
            }
        }

        // 填写奇数位
        for(int j = 1; j < res.size(); j += 2){
            res[j] = p.second;
            p.first--;
            if(p.first == 0){
                p = pq.top();
                pq.pop();
            }
        }
        return res;
    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

[callmeerika]

思路

堆排序 + 隔位插入

代码

var Heap = function (arr) {
  this.queue = [];
  this.size = 0;
  this.init(arr);
};
Heap.prototype.init = function (arr) {
  this.size = arr.length;
  this.queue = new Array(arr.length + 1);
  let i = 1;
  for (let val of arr) {
    this.queue[i++] = val;
  }
  this.buildHeap();
};
Heap.prototype.buildHeap = function () {
  for (let i = this.size >> 1; i > 0; i--) {
    this.goDown(i);
  }
};
Heap.prototype.goDown = function (i) {
  let temp = this.queue[i];
  while (i << 1 <= this.size) {
    let child = i << 1;
    // child < size 表示当前元素有右节点
    if (
      child < this.size &&
      this.queue[child + 1].value > this.queue[child].value
    ) {
      child++;
    }
    if (temp.value >= this.queue[child].value) break;
    this.queue[i] = this.queue[child];
    i = child;
  }
  this.queue[i] = temp;
};
Heap.prototype.isEmpty = function () {
  return this.size <= 0;
};
Heap.prototype.pop = function () {
  if (this.isEmpty()) {
    return null;
  }
  let res = this.queue[1];
  this.queue[1] = this.queue.pop();
  this.size--;
  this.goDown(1);
  return res;
};

var rearrangeBarcodes = function (barcodes) {
  const n = barcodes.length;
  const hash = new Map();
  for (let barcode of barcodes) {
    hash.set(barcode, (hash.get(barcode) || 0) + 1);
  }
  let arr = [];
  for (let [key, value] of hash.entries()) {
    arr.push({
      key: key,
      value: value,
    });
  }
  let heap = new Heap(arr);
  const max = heap.queue[1].value;
  const gap = Math.ceil(n / max);
  let tmp = heap.pop();
  const res = new Array(max*gap).fill(0);
  for (let i = 0; i < gap; i++) {
    for (let j = 0; j < max; j++) {
      let index = i + j * gap;
      if (tmp.value === 0) {
        tmp = heap.pop();
      }
      res[index] = tmp.key;
      tmp.value -= 1;
      if(heap.isEmpty()&&tmp.value===0) return res.filter(vv=>vv > 0);
    }
    if(heap.isEmpty()&&tmp.value===0) return res.filter(vv=>vv > 0);
  }
};

复杂度

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

[ZJP1483469269]

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
            n = len(barcodes)

            p = []
            cnt = Counter(barcodes)
            for x , cn in cnt.items():
                heappush(p , (-cn , x))
            ans = []
            while len(p) > 1:
                cn1 , x1 = heappop(p)
                cn2,x2 = heappop(p)
                ans.append(x1)
                ans.append(x2)
                cn1 += 1
                cn2 += 1
                if cn1:
                    heappush(p,(cn1 , x1))
                if cn2:
                    heappush(p,(cn2 , x2))
            if p:
                ans.append(p[0][1])

            return ans

[charlestang]

思路

排好序，按照贪心策略来构造序列。

代码

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        n = len(barcodes)
        freq = Counter(barcodes)
        stats = sorted(freq, key=lambda x: -freq[x])
        barcodes = []
        for k in stats:
            barcodes += [k] * freq[k]
        ans = [None for _ in range(n)]
        l = len(ans[::2])
        ans[::2] = barcodes[:l]
        ans[1::2] = barcodes[l:]
        return ans

[Aobasyp]

思路 贪心 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;
}

} 时间复杂度：O(NlogK) 空间复杂度：O(K)

[declan92]

思路

1. 对元素出现频率进行排序;
2. 每次取出频率最高的两个元素,加入结果数组,取出后更新频率;

java

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        int[] ans = new int[barcodes.length];
        Map<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
        for (int i : barcodes) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        for (int key : map.keySet()) {
            pq.offer(key);
        }
        int index = 0;
        while (true) {
            int key1 = pq.poll();
            int val1 = map.get(key1);
            int key2 = pq.poll();
            int val2 = map.get(key2);
            if (val1 != 0) {
                ans[index++] = key1;
                map.put(key1, val1 - 1);
                pq.offer(key1);
            } else {
                break;
            }
            if (val2 != 0) {
                ans[index++] = key2;
                map.put(key2, val2 - 1);
                pq.offer(key2);
            } else {
                break;
            }
        }
        return ans;
    }
}

时间:O(n*logn),n为数组长度; 空间:O(k),k为数组不重复数个数;

[moirobinzhang]

Code:

public int[] RearrangeBarcodes(int[] barcodes) {
    if (barcodes == null || barcodes.Length < 3)
        return barcodes;

    Dictionary<int, int> mappingDict = new Dictionary<int, int>();
    foreach(int barcode in barcodes)
    {
        if (!mappingDict.ContainsKey(barcode))
            mappingDict.Add(barcode, 0);
        mappingDict[barcode]++;            
    }

    int[] res = new int[barcodes.Length];
    int cursorIndex = 1;

    foreach(var item in mappingDict.OrderBy(m => m.Value))
    {

        for(int i = 0; i < item.Value; i++)
        {
            if (cursorIndex >= barcodes.Length)
                cursorIndex = 0;

            res[cursorIndex] = item.Key;
            cursorIndex += 2;
        }
    }        

    return res;
}

[hdyhdy]

func rearrangeBarcodes(barcodes []int) []int {
    //记录每个数字的数量
    cntr:=map[int]int{}
    for _,v :=range barcodes{
        cntr[v]++
    }

   //初始化heap，将各数字的数量和值push
   //按照出现的次数排序
    myHp:=&hp{}
    for k,v:=range cntr{
        heap.Push(myHp,[]int{v,k})
    }

    ans:=[]int{}
    tmpq:=[][]int{}

    for myHp.Len()>0{
        //top就是次数比较多的数字的内容
        top:=heap.Pop(myHp).([]int)
        ans=append(ans,top[1])

        //tmp就是将top对应的数字的内容次数变少版写入
        tmpq=append(tmpq,[]int{top[0]-1,top[1]})
        //tmp如果有两个内容了（答案写入两个不同的数字了）
        if len(tmpq)==2{
            //一个一个tmp在写入堆里面（如果次数还没有用完）
            for len(tmpq)>0{
                p:=tmpq[0]
                tmpq=tmpq[1:]
                if p[0] > 0{
                    heap.Push(myHp,p)
                }
            }
        }
    }
    return ans
}

type hp [][]int
func (h hp)Len()int{return len(h)}
func (h hp)Less(i,j int)bool{return h[i][0]>h[j][0]}
func (h hp)Swap(i,j int){h[i],h[j]=h[j],h[i]}
func (h *hp)Pop()interface{}{
    a:=*h
    n:=len(a)
    v:=a[n-1]
    *h=a[:n-1]
    return v
}
func (h *hp)Push(v interface{}){*h=append(*h,v.([]int))}

[Richard-LYF]

class Solution: def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]: n = len(barcodes) d = {}

    for i in barcodes:
        if i not in d:
            d[i] = 1
        else:
            d[i] += 1

    cur = []
    l = sorted(d.items(), key = lambda x:-x[1])

    res = [0] * len(barcodes)
    for i in l:
        cur += [i[0]] * i[1]
    j = 0

    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

o(n +klogk) on

[ggohem]

Code:

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

复杂度：

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

[guangsizhongbin]

func rearrangeBarcodes(barcodes []int) []int { m := make(map[int]int) for i := 0; i < len(barcodes); i++ { m[barcodes[i]]++ } n := make([]Node, 0, len(m)) for k, v := range m { n = append(n, Node{k, v}) } sort.Slice(n, func(i, j int) bool { return n[i].count > n[j].count }) ret := make([]int, len(barcodes)) start := 0 for _, v := range n { val, count := v.val, v.count for count > 0 { ret[start] = val start += 2 count-- if start >= len(barcodes) { start = 1 } } } return ret }

type Node struct { val int count int }

[hx-code]

class Solution: def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]: n = len(barcodes) freq = Counter(barcodes) stats = sorted(freq, key=lambda x: -freq[x]) barcodes = [] for k in stats: barcodes += [k] * freq[k] ans = [None for _ in range(n)] l = len(ans[::2]) ans[::2] = barcodes[:l] ans[1::2] = barcodes[l:] return ans

[yetfan]

思路 排序+间隔插入

代码

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        counter = dict(collections.Counter(barcodes))
        #按出现次数统计元素
        sortedCounter = sorted( counter, key=lambda k: 0 - counter[k])
        barcodes = []
        #重新排序
        for i in sortedCounter:
            barcodes += [i] * counter[i]

        arrangedBarcodes = [None for _ in range(len(barcodes))]
        #间隔插入
        arrangedBarcodes[::2] = barcodes[:len(arrangedBarcodes[::2])]
        arrangedBarcodes[1::2] = barcodes[len(arrangedBarcodes[::2]):]

        return arrangedBarcodes

复杂度 时间 O(nlogn) 空间 O(n)

[tian-pengfei]

struct cmp{

    public:
    bool operator()(pair<int,int> a ,pair<int,int> b){

        return a.second<b.second;
    }
};
class Solution {
public:
    //因为一定有答案，所以某一个数字最多是n/2 向上取整 221话u  2 1 2 ；
    //所以谁多先排谁，且与上一个排列的不相同 ，把某一个拍完之后就先忽略这个数字，然后从剩下中调个数最多的数字。必然不能重复
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        vector<int> re;
        priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> q;
        sort(barcodes.begin(),barcodes.end());
        int count;
        for (int i = 0; i < barcodes.size(); ++i) {

            if(i>0&&barcodes[i-1]!= barcodes[i]){
                q.emplace(barcodes[i-1],count);
                count=1;
                continue;
            }
            count++;
        }
        q.emplace(barcodes[barcodes.size()-1],count);

        int a = q.top().first;
        int b  = q.top().second;
        q.pop();
        if(b>1){
         q.emplace(a,b-1);
        }
        int last =a;
        re.push_back(last);

        while (!q.empty()){
            int x=0;
            int y=0;
            if(last!=q.top().first){
                x= q.top().first;
                y = q.top().second;
                q.pop();
            }else{
                pair<int,int> tmp = q.top();
                q.pop();
                if(q.empty())break;
                x= q.top().first;
                y = q.top().second;
                q.pop();
                q.push(tmp);
            }
            re.push_back(x);
            last = x;
            if(y>1){
                q.emplace(x,y-1);
            }
        }

        return re;

    }
};

[Hacker90]

class Solution: def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]: counter = dict(collections.Counter(barcodes))

按出现次数统计元素

    sortedCounter = sorted( counter, key=lambda k: 0 - counter[k])
    barcodes = []
    #重新排序
    for i in sortedCounter:
        barcodes += [i] * counter[i]

    arrangedBarcodes = [None for _ in range(len(barcodes))]
    #间隔插入
    arrangedBarcodes[::2] = barcodes[:len(arrangedBarcodes[::2])]
    arrangedBarcodes[1::2] = barcodes[len(arrangedBarcodes[::2]):]

    return arrangedBarcodes

复杂度 时间 O(nlogn) 空间 O(n)

[xinhaoyi]

class Solution { public int[] rearrangeBarcodes(int[] barcodes) { int length = barcodes.length; // 1 <= barcodes[i] <= 10000，所以定义numToCount数组长度为10001 int[] numToCount = new int[10001]; //统计每个字符出现的次数 for (int i = 0; i < length; i++) { numToCount[barcodes[i]]++; } int max = 0, maxNum = 0; //找出出现次数最多的那个字符 for (int i = 0; i < length; i++) { if (numToCount[barcodes[i]] > max) { max = numToCount[barcodes[i]]; maxNum = barcodes[i]; } } //到这一步说明他可以使得两相邻的字符不同，我们随便返回一个结果，res就是返回 int[] res = new int[length]; int index = 0; //先把出现次数最多的字符存储在数组下标为偶数的位置上 while (numToCount[maxNum]-- > 0) { res[index] = maxNum; index += 2; } //然后再把剩下的字符存储在其他位置上 for (int i = 0; i < length; i++) { while (numToCount[barcodes[i]]-- > 0) { if (index >= res.length) { index = 1; } res[index] = barcodes[i]; index += 2; } } return res; } }

[fornobugworld]

class Solution: def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]: counter = dict(collections.Counter(barcodes))

按出现次数统计元素

    sortedCounter = sorted( counter, key=lambda k: 0 - counter[k])
    barcodes = []
    #重新排序
    for i in sortedCounter:
        barcodes += [i] * counter[i]

    arrangedBarcodes = [None for _ in range(len(barcodes))]
    #间隔插入
    arrangedBarcodes[::2] = barcodes[:len(arrangedBarcodes[::2])]
    arrangedBarcodes[1::2] = barcodes[len(arrangedBarcodes[::2]):]

    return arrangedBarcodes

[GaoMinghao]

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> counts = new HashMap<>();
        PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return counts.get(o2)-counts.get(o1);
            }
        });
        for(int barcode:barcodes)
            counts.put(barcode, counts.getOrDefault(barcode,0)+1);
        for(int num:counts.keySet())
            heap.offer(num);
        int idx = 0;
        while (heap.size()>1) {
            int first = heap.poll(), second = heap.poll();
            barcodes[idx++] = first;
            barcodes[idx++] = second;
            counts.put(first, counts.get(first)-1);
            counts.put(second, counts.get(second)-1);
            if(counts.get(first)>0)
                heap.offer(first);
            if(counts.get(second)>0)
                heap.offer(second);
        }
        if(heap.size()>0)
            barcodes[idx++] = heap.poll();
        return barcodes;
    }
}

[ZacheryCao]

Idea

heap

Code

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        heap = []
        count = collections.Counter(barcodes)
        ans = []
        for i in count:
            heapq.heappush(heap, (-count[i], i))
        while len(heap)>1:
            c1,b1 = heapq.heappop(heap)
            c2,b2 = heapq.heappop(heap)
            ans.append(b1)
            ans.append(b2)
            c1+=1
            c2+=1
            if c1!=0:
                heapq.heappush(heap, (c1,b1))
            if c2!=0:
                heapq.heappush(heap,(c2, b2))
        if heap:
            ans.append(heap[0][1])
        return ans

Complexity:

Time: O(N log k). k: unique items. N total length of barcodes Space: O(k)

[for123s]

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int,int>num2cnt;
        int n=barcodes.size();
        for(int i=0;i<n;i++){
            num2cnt[barcodes[i]]++;
        }
        priority_queue<pair<int,int>>maxHeap;
        for(auto mPair:num2cnt)maxHeap.push({mPair.second,mPair.first});
        vector<int>ans;
        while(maxHeap.empty()==false){
            auto [firstCnt,firstNum]=maxHeap.top();maxHeap.pop();
            if(ans.empty()||ans.back()!=firstNum){
                ans.push_back(firstNum);
                firstCnt--;
                if(firstCnt==0)continue;
                maxHeap.push({firstCnt,firstNum});
            }else {
                auto [secondCnt,secondNum]=maxHeap.top();maxHeap.pop();
                maxHeap.push({firstCnt,firstNum});
                ans.push_back(secondNum);
                secondCnt--;
                if(secondCnt==0)continue;
                maxHeap.push({secondCnt,secondNum});
            }

        }
        return ans;
    }
};

[taojin1992]

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        int[] rearranged = new int[barcodes.length];

        Map<Integer, Integer> valFreqMap = new HashMap<>();
        PriorityQueue<Integer> valPq = new PriorityQueue<>((a, b) -> (valFreqMap.get(b) - valFreqMap.get(a))); // sorted by freq reversely

        for (int barcode : barcodes) {
            valFreqMap.put(barcode, valFreqMap.getOrDefault(barcode, 0) + 1);
        }

        for (int key : valFreqMap.keySet()) {
            valPq.offer(key);
        }

        int cur = 0;
        // 1,1,1,2,3

        // 1-3
        // 2-1
        // 3-1

        // 1,2

        // 1-2
        // 3-1

        // 1,2, 1,3
        // 1-1
        // 1,2,1,3,1

        // because we need to poll two elements
        while (valPq.size() > 1) {
            // Heap has O(log(k)) time complexity to insert and delete element
            int first = valPq.poll();
            int second = valPq.poll();
            rearranged[cur++] = first;
            rearranged[cur++] = second;

            // modify map
            valFreqMap.put(first, valFreqMap.get(first) - 1);
            valFreqMap.put(second, valFreqMap.get(second) - 1);

            // if freq > 0, put back to pq; otherwise, no need to put back
            if (valFreqMap.get(first) > 0) {
                valPq.offer(first);
            }

            if (valFreqMap.get(second) > 0) {
                valPq.offer(second);
            }  
        }
        // if we have odd number
        if (valPq.size() == 1) {
            rearranged[cur] = valPq.poll();
        }

        return rearranged;
    }
}

[falconruo]

思路:

hashmap + sort

复杂度分析:

• 时间复杂度: O(N + KlogK), N为barcodes的长度, K为不同barcode的数目
• 空间复杂度: O(N)

代码(C++):

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int, int> freq;
        int n = barcodes.size();
        for (auto v : barcodes)
            freq[v]++;

        priority_queue<pair<int, int>> pq;

        for (auto f : freq)
            pq.push({f.second, f.first});

        vector<int> tmp;
        while (!pq.empty()) {
            pair<int, int> top = pq.top();
            pq.pop();

            for (int i = 0; i < top.first; ++i)
                tmp.push_back(top.second);
        }

        vector<int> res(n);

        int j = 0;
        for (int i = 0; i < n; i += 2)
            res[i] = tmp[j++];

        for (int i = 1; i < n; i += 2)
            res[i] = tmp[j++];

        return res;
    }
};