LeetCode动画 | 1054.距离相等的条形码
LeetCode动画 | 1054.距离相等的条形码
今天分享一个LeetCode题，题号是1054，标题是距离相等的条形码，题目标签是堆和排序。
本题使用堆的数据结构去解这道题，同时画了算法动画视频，记得收看哦。还有为了提升时间上的效果，后面也出了完全使用数组结构去解这道题，也使用了空间换取时间的小技巧。
题目描述
在一个仓库里，有一排条形码，其中第 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解题
我们做LeetCode题目目的是为了锻炼各种各样的数据结构，当然可以为了提升时间的效果仅仅做数组的结构。
题目标签是堆和排序，那么我们就用堆和堆排序的思想去做这道题。
我们先创建散列表，在Java库里面关于散列表的类有很多，在这里可以使用HashMap和TreeMap。但我更偏向TreeMap这个类，TreeMap类（红黑树）在时间上和空间上在数据量很大的角度上会省很多，而且在图论建模中，我也经常偏向TreeMap类。
创建TreeMap类对象，去统计barcode出现的次数，代码如下：
TreeMap<Integer, Integer> map = new TreeMap<>(); // 红黑树
for (int barcode : barcodes)
map.put(barcode, map.getOrDefault(barcode, 0) + 1);然后我们再看输入示例，假设输入示例是[1, 1, 1, 1, 2, 2, 3]，题目要求重新排列条形码，不能出现两个相邻的条形码是相等的。
我们可以这样设计，将出现最多次数的条形码先填充到res数组偶数位上，最多填满偶数位。然后将其它的条形码继续填充偶数位和奇数位。可以用最大堆的思想。
基于最大堆的优先队列，在Java库里面有这样的一个类，是PriorityQueue类。
它默认是最小堆的数据结构，如果想定义成最大堆，可以自定义Comparator类，代码如下：
PriorityQueue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o2.count - o1.count; // 最大堆
}
});或者使用java8版本以及上版本的Lamdba表达式函数
PriorityQueue<Node> queue = new PriorityQueue<>(
(a, b) -> b.count - a.count // lambda表达式函数 jdk8及以上版本
);定义好了最大堆的优先队列，可以遍历TreeMap类的键值对，按照统计次数排序添加到队列中，代码如下：
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
Node node = new Node(entry.getKey(), entry.getValue());
queue.add(node); // node对象包含两个属性，barcode和count
}然后取最大堆的顶点去填充到返回数组，先按偶数位填充，再按奇数位填充，代码如下：
int index = 0;
while (queue.size() > 0) {
Node node = queue.poll();
while (node.count != 0) {
if (index >= res.length) index = 1;
res[index] = node.code;
node.count--;
index += 2;
}
}动画
Code：使用基于最大堆的优先队列
import java.util.*;
public class Solution {
private class Node {
int code, count;
public Node(int code, int count) {
this.code = code;
this.count = count;
}
}
public int[] rearrangeBarcodes(int[] barcodes) {
// 创建返回结果
int[] res = new int[barcodes.length];
TreeMap<Integer, Integer> map = new TreeMap<>(); // 红黑树
for (int barcode : barcodes)
map.put(barcode, map.getOrDefault(barcode, 0) + 1);
// 创建基于最大堆的优先队列
PriorityQueue<Node> queue = new PriorityQueue<>(
(a, b) -> b.count - a.count // lambda表达式函数 jdk8及以上版本
);
// 与下面等价
// PriorityQueue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
// @Override
// public int compare(Node o1, Node o2) {
// return o2.count - o1.count;
// }
// });
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
Node node = new Node(entry.getKey(), entry.getValue());
queue.add(node);
}
int index = 0;
while (queue.size() > 0) {
Node node = queue.poll();
while (node.count != 0) {
if (index >= res.length) index = 1;
res[index] = node.code;
node.count--;
index += 2;
}
}
return res;
}
public static void main(String[] args) {
int[] barcodes = new int[]{1, 1, 1, 1, 2, 2, 3, 3};
int[] bar = new Solution().rearrangeBarcodes(barcodes);
for (int i = 0; i < bar.length - 1; i++) {
if (bar[i] == bar[i + 1]) System.out.println("重复");
}
}
}如果为了追求时间上的效果，可以完全使用数组的数据结构，还有空间换取时间的小技巧。
我们再看题目描述，描述给出了提示：
1 <= barcodes.length <= 10000
1 <= barcodes[i] <= 10000说明限定了数组的长度范围和数组值的大小，可以完全使用直接寻址表去收集barcode出现的次数，访问时间复杂度是O(1)，代码如下：
public class Solution {
public int[] rearrangeBarcodes(int[] barcodes) {
// 创建直接寻址表
int[] address = new int[10001];
for (int barcode : barcodes)
address[barcode]++;
// 。。。
return barcodes;
}
}以后想访问barcode还有多少次数都可以通过address数组的下标直接访问，速度快得不能再快了。
然后我们再看输入示例，假设输入示例是[1, 1, 1, 1, 2, 2, 2, 2, 2]，很明显，条形码第一个数必须是放2，如果先放1的话，后面就没有其它的数字去隔离2了。
所以在代码中我们要找出最大的那一位barcode，代码如下：
// 找到最大的那一位barcode
int maxCode = 0, maxCount = 0;
for (int i = 0; i < address.length; i++) {
if (maxCount < address[i]) {
maxCode = i;
maxCount = address[i];
}
}可以为了省空间，看前面的代码有没有一个对象已经失去了存在的意义，然后看后面是否是可以利用的。
barcodes数组在创建直接寻址表之后已经失去了意义，但是在返回函数类型中需要barcodes类型返回，而且数组长度也一样，可以用这个barcodes返回。
然后使用barcodes先填充最大次数的那一位barcode，每次填充需隔离一个为空，即只填充偶数位，填充完了就继续填充其它的barcode。当index超出barcodes数组的长度的时候，可以接着填充奇数位。
Code：完全使用数组
/**
* 1 <= barcodes.length <= 10000
* 1 <= barcodes[i] <= 10000
*/
// 数组
public class Solution {
public int[] rearrangeBarcodes(int[] barcodes) {
// 创建直接寻址表
int[] address = new int[10001];
for (int barcode : barcodes)
address[barcode]++;
// 找到最大的那一位barcode
int maxCode = 0, maxCount = 0;
for (int i = 0; i < address.length; i++) {
if (maxCount < address[i]) {
maxCode = i;
maxCount = address[i];
}
}
int index = 0;
// 先填充最大的那一位barcode
for (; address[maxCode] > 0; index += 2) {
barcodes[index] = maxCode;
address[maxCode]--;
}
// 继续填充后面的code
for (int i = 1; i < address.length; i++) {
while (address[i] > 0) {
if (index >= barcodes.length) index = 1;
barcodes[index] = i;
address[i]--;
index += 2;
}
}
return barcodes;
}
}
腾讯云开发者
