【优先队列】【堆排序实现优先队列】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
我的解法一
-
dfs暴力枚举
-
毫无疑问TLO了。。
class Solution {
List<Integer> ans;
List<Integer> path = new ArrayList<>();
boolean[] visit;
int[] barcodes;
public void dfs() {
if(path.size() >= barcodes.length) {
ans = new ArrayList(path);
return ;
}
for(var i = 0; i < barcodes.length; i++) {
if ((path.size() == 0) || (!visit[i] && barcodes[i] != path.get(path.size()-1))) {
path.add(barcodes[i]);
visit[i] = true;
dfs();
path.remove(path.size()-1);
visit[i] = false;
}
}
}
public int[] rearrangeBarcodes(int[] barcodes) {
this.barcodes = barcodes;
this.visit = new boolean[barcodes.length];
dfs();
return ans.stream().mapToInt(Integer::valueOf).toArray();
}
}
我的解法二
- 维护一个hash数组，每次都去遍历一遍获取最大值和次大值加入结果数组
- 也TLO了。。
class Solution {
public int[] rearrangeBarcodes(int[] barcodes) {
var ans = new ArrayList<Integer>();
var hash = new int[10000+1];
for(var i = 0; i < barcodes.length; i++) {
hash[barcodes[i]]++;
}
while(ans.size() < barcodes.length) {
var maxPos = 0;
var maxCount = 0;
for(var i = 0; i <= 10000; i++) {
if(hash[i] > maxCount) {
maxCount = hash[i];
maxPos = i;
}
}
ans.add(maxPos);
hash[maxPos]--;
if(ans.size() >= barcodes.length) {
break;
}
var next = maxPos;
while(hash[next] <= 0 || next == maxPos) {
next = (next + 1) % 10000;
}
hash[next]--;
ans.add(next);
}
return ans.stream().mapToInt(Integer::valueOf).toArray();
}
}
优先队列
- 和上面的思想大同小异，获取最大值和次大值加入结果数组
- 以前没接触过优先级队列，会自动对加入数据进行定义排序
class Solution {
public int[] rearrangeBarcodes(int[] barcodes) {
var hash = new int[10000+1];
for (int barcode : barcodes) {
hash[barcode]++;
}
var q = new PriorityQueue<int[]>((a, b) -> {
if(b[1] != a[1]) {
return b[1] - a[1];
}
return a[0] - b[0];
});
for(var i = 0; i <= 10000; i++) {
if(hash[i] > 0) {
q.add(new int[]{i, hash[i]});
}
}
var index = 0;
while(!q.isEmpty()) {
var first = q.remove();
first[1]--;
barcodes[index++] = first[0];
if(!q.isEmpty()) {
var second = q.remove();
second[1]--;
barcodes[index++] = second[0];
if(second[1] > 0) {
q.add(second);
}
}
if(first[1] > 0) {
q.add(first);
}
}
return barcodes;
}
}
堆排序
- 一说到动态获取最大、最小值，那么堆排序肯定是少不了的
- 因为是获取最大值，所以使用大顶堆
- 如果最大值和前面的重复，则选择第二大的：选择第二大的方法就是将堆的最后一个元素和第一个元素替换然后计算 n - 2 的自底向上即可
class Solution {
int[][] heap;
// 大顶堆自下而上
public void downToUp(int n) {
for(var i = n/2; i >= 0; i--) {
if(heap[i * 2][1] > heap[i][1]) {
var dumy = heap[i * 2];
heap[i * 2] = heap[i];
heap[i] = dumy;
} else if(i * 2 + 1 <= n
&& heap[i * 2 + 1][1] > heap[i][1]) {
var dumy = heap[i * 2 + 1];
heap[i * 2 + 1] = heap[i];
heap[i] = dumy;
}
}
}
public int[] rearrangeBarcodes(int[] barcodes) {
var len = barcodes.length;
var hash = new int[10000+1];
var map = new HashMap<Integer, Integer>();
for(var i = 0; i < len; i++) {
map.put(barcodes[i], map.getOrDefault(barcodes[i], 0) + 1);
}
var count = 0;
this.heap = new int[map.size()][2];
for(var item : map.entrySet()) {
heap[count++] = new int[]{item.getKey(), item.getValue()};
}
var index = 0;
while(index < len) {
// 找出最大
downToUp(count-1);
if(index == 0 || barcodes[index-1] != heap[0][0]) {
barcodes[index++] = heap[0][0];
heap[0][1]--;
} else {
// 找出第二大
var dumy = heap[0];
heap[0] = heap[count-1];
heap[count-1] = dumy;
downToUp(count-2);
barcodes[index++] = heap[0][0];
heap[0][1]--;
}
}
return barcodes;
}
}