1054. 距离相等的条形码

难度中等

在一个仓库里,有一排条形码,其中第 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]

提示:

  • 1 <= barcodes.length <= 10000
  • 1 <= barcodes[i] <= 10000

# 堆(优先队列)

每次获取次数最多的元素 firstfirst

  • firstfirst 与结果集上一元素 ans[k1]ans[k - 1] 相等,

    则需要获取 secondsecondans[k]=secondans[k] = second,只有 secondsecond 的次数 >0> 0 才会入队列

  • firstfirstans[k1]ans[k - 1] 不相等,

    则直接 $ ans [k] = first$,只有 firstfirst 的次数 >0>0 才会入队列

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        int n = barcodes.length;
        int[] cnt = new int[10001];
        for (int barcode : barcodes) {
            cnt[barcode]++;
        }
        //[元素,次数]
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] > 0) {
                minHeap.add(new int[]{i, cnt[i]});
            }
        }
        int k = 0;
        int[] ans = new int[n];
        while (!minHeap.isEmpty()) {
            int[] first = minHeap.poll();
            // 说明还是当前元素
            if (k > 0 && first[0] == ans[k - 1]) {
                int[] second = minHeap.poll();
                ans[k++] = second[0];
                second[1]--;
                minHeap.add(first);
                if (second[1] > 0) {
                    minHeap.add(second);
                }
                continue;
            }
            if (k == n) {
                break;
            }
            first[1]--;
            ans[k++] = first[0];
            if (first[1] > 0) {
                minHeap.add(first);
            }
        }
        return ans;
    }
}

# 哈希表 + 计数 + 排序

每次获取次数最多的元素 firstfirst,首先每次填入偶数位,偶数位填完之后从奇数位开始填入。

题意说必有解,说明数组中频率最高的元素其计数不超总长的一半,极限情况下:nn 为奇数时最多 n/2+1n/2 + 1nn 为偶数时最多 n/2n/2

所以排序后对半开就能交替分开

例如:1,1,1,1,2,2,3,31,1,1,1,2,2,3,3

  • 1,_,1,_,1,_,1,_1,\,\_\,,1,\,\_\,,1,\,\_\,,1,\,\_

    1,2,1,2,1,_,1,_1,2,1,2,1,\,\_\,,1,\,\_

    1,2,1,2,1,3,1,31,2,1,2,1,3,1,3

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        // 按次数排序
        int n = barcodes.length;
        int[] cnts = new int[10001];
        for (int barcode : barcodes) {
            cnts[barcode]++;
        }
        Integer[] idx = new Integer[10001];
        for (int i = 0; i < 10001; i++) {
            idx[i] = i;
        }
        Arrays.sort(idx, (o1, o2) -> cnts[o2] - cnts[o1]);
        int i = 0;
        int[] ans = new int[n];
        int k = 0;
        int d = 0;
        while (d < n) {
            // 填入 cnt 次
            int cnt = cnts[idx[k]];
            while (i < n && cnt-- > 0) {
                ans[i] = idx[k];
                i += 2;
                d++;
            }
            // 偶数填完了,从奇数开始,所以必然有解
            if (i >= n) {
                i = 1;
            }
            if (cnt <= 0) {
                k++;
            } else {
                cnts[idx[k]] = cnt;
            }
        }
        return ans;
    }
}

# 优化

实际上我们不需要对所有元素和出现次数排序,只需要知道「哪个元素的出现次数最多」,剩下元素无所谓,都是用来插空的

这样,我们可以在统计次数的过程中记录下次数最多的元素,然后先安排它,再安排其他元素按照奇偶插空,不需要排序

class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        int n = barcodes.length;
        // 最多的元素及其字数
        int[] first = new int[2];
        int[] cnts = new int[10001];
        for (int barcode : barcodes) {
            if (++cnts[barcode] > first[1]) {
                first[1] = cnts[barcode];
                first[0] = barcode;
            }
        }
        cnts[first[0]] = 0;
        int[] ans = new int[n];
        int k = 0;
        int d = 0;
        int i = 0;
        while (d < n) {
            // 按照奇偶插入
            while (first[1]-- > 0) {
                ans[k] = first[0];
                d++;
                k += 2;
                if (k >= n) {
                    k = 1;
                }
            }
            if (d == n) {
                break;
            }
            // 寻找下一个次数不为 0 的元素
            cnts[i] = 0;
            while (cnts[i] == 0) {
                i++;
            }
            first[0] = i;
            first[1] = cnts[i];
        }
        return ans;
    }
}