难度中等
在一个仓库里,有一排条形码,其中第 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
# 堆(优先队列)
每次获取次数最多的元素
-
若 与结果集上一元素 相等,
则需要获取 ,,只有 的次数 才会入队列
-
若 与 不相等,
则直接 $ ans [k] = first$,只有 的次数 才会入队列
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; | |
} | |
} |
# 哈希表 + 计数 + 排序
每次获取次数最多的元素 ,首先每次填入偶数位,偶数位填完之后从奇数位开始填入。
题意说必有解,说明数组中频率最高的元素其计数不超总长的一半,极限情况下: 为奇数时最多 ; 为偶数时最多 ,
所以排序后对半开就能交替分开
例如:
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; | |
} | |
} |