# 1054. Distant Barcodes
###### tags: `Leetcode` `Medium` `Priority Queue` `Greedy` `Task Scheduler`
Link: https://leetcode.com/problems/distant-barcodes/
## 思路
和[0767. Reorganize String](https://hackmd.io/Cs2YBT2RQHOFLNcLLFBPOQ)很像
### 思路一 $O(NlogN)$ $O(N)$
先统计每个数字出现的次数，然后对次数进行排序，按照次数从大到小拿元素，先排偶数位再排奇数位
### 思路二 $O(N)$ $O(N)$
由于最多有10000个不同的数字，因此可以使用桶排序，因此不需要用priority queue，所以不需要$O(NlogN)$
## Code
### 思路一

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int barcode:barcodes){
            map.put(barcode, map.getOrDefault(barcode, 0)+1);
        }
        Queue<int[]> pq = new PriorityQueue<>((a,b)->(b[1]-a[1]));
        for(Map.Entry<Integer,Integer> e: map.entrySet()){
            pq.add(new int[]{e.getKey(), e.getValue()});
        }
        int[] ans = new int[barcodes.length];
        int pos = 0;
        while(!pq.isEmpty()){
            int[] curr = pq.poll();
            int num = curr[0];
            int freq = curr[1];
            while(freq > 0){
                ans[pos] = num;
                pos += 2;
                if(pos >= ans.length){
                    pos = 1;
                }
                freq--;
            }
        }
        return ans;
    }
}

### 思路二

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        int[] freq = new int[10001];
        int maxFreq = 0, maxNum = 0;
        for(int barcode:barcodes){
            freq[barcode]++;
            if(freq[barcode]>maxFreq){
                maxFreq = freq[barcode];
                maxNum = barcode;
            }
        }
        int[] ans = new int[barcodes.length];
        int pos = 0;
        for(int i = 0;i < 10001;i++){
            int n = i==0?maxNum:i;
            while(freq[n] > 0){
                ans[pos] = n;
                pos+=2;
                if(pos >= ans.length) pos=1;
                freq[n]--;
            }
        }
        return ans;
    }
}