[LeetCode] 1054. Distant Barcodes

In a warehouse, there is a row of barcodes, where the ith barcode is barcodes[i].

Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.

Example 1:

Input: barcodes = [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]

Example 2:

Input: barcodes = [1,1,1,1,2,2,3,3]
Output: [1,3,1,3,1,2,1,2]

Constraints:

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

距离相等的条形码。

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/distant-barcodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是排序 + 贪心。因为要确保结果数组内不能有相同元素相邻，所以思路一开始一定是优先放出现次数最多的元素，再来是次多的。做法是先用hashmap统计不同元素分别都出现了多少次，然后创建一个最大堆，把所有元素的key和出现次数放入。这样每次优先被弹出的元素一定是出现次数最多的元素。同时我们需要另外一个变量记录上一个被写入结果集的key是什么，如果当前出现次数最多的key刚刚被写过一次，则从最大堆中再弹出一个key写入结果集。否则类似如下这个case是过不去的，第一次写入一个1之后，1仍然是出现次数最多的元素。

[1,1,1,1,2,2,3,3]

时间O(nlogn)

空间O(n)

Java实现

 1 class Solution {
 2     public int[] rearrangeBarcodes(int[] barcodes) {
 3         HashMap<Integer, Integer> map = new HashMap<>();
 4         for (int num : barcodes) {
 5             map.put(num, map.getOrDefault(num, 0) + 1);
 6         }
 7 
 8         // [key, value]
 9         // maxHeap
10         PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
11         for (int key : map.keySet()) {
12             queue.offer(new int[] { key, map.get(key) });
13         }
14 
15         int lastKey = 0;
16         List<Integer> res = new ArrayList<>();
17         while (!queue.isEmpty()) {
18             int[] first = queue.poll();
19             int key = first[0];
20             int value = first[1];
21             if (key != lastKey) {
22                 res.add(key);
23                 value--;
24                 if (value > 0) {
25                     queue.offer(new int[] { key, value });
26                 }
27                 lastKey = key;
28             } else {
29                 int[] second = queue.poll();
30                 int secondKey = second[0];
31                 int secondValue = second[1];
32                 res.add(secondKey);
33                 secondValue--;
34                 if (secondValue > 0) {
35                     queue.offer(new int[] { secondKey, secondValue });
36                 }
37                 lastKey = secondKey;
38                 queue.offer(first);
39             }
40         }
41         int[] list = new int[res.size()];
42         for (int i = 0; i < list.length; i++) {
43             list[i] = res.get(i);
44         }
45         return list;
46     }
47 }

这道题还有一个思路，还是需要用hashmap统计每个不同元素的出现次数，但是写入的时候，是先把出现次数最多的元素写入所有偶数的index，再把次多的元素写入所有奇数的index。但是这个思路的时间复杂度并没有更好，因为还是需要涉及到出现次数的排序。

LeetCode 题目总结