Java | LeetCode
Задача: 1054. Distant Barcodes
Сложность: medium
На складе имеется ряд штрих-кодов, где i-й штрих-код - barcodes[i]. Переставьте штрих-коды так, чтобы два соседних штрих-кода не были одинаковыми. Вы можете вернуть любой ответ, и гарантируется, что ответ существует.
Пример:
Input: barcodes = [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]
👨💻 Алгоритм:
1⃣Подсчитай частоту каждого штрих-кода.
Помести все штрих-коды в максимальную кучу на основе их частоты.
2⃣Извлекай штрих-коды из кучи, чередуя их, чтобы два соседних штрих-кода не были одинаковыми.
3⃣Если куча становится пустой, помести временно сохранённый штрих-код обратно в кучу.
😎 Решение:
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class Solution {
public int[] rearrangeBarcodes(int[] barcodes) {
Map<Integer, Integer> count = new HashMap<>();
for (int barcode : barcodes) {
count.put(barcode, count.getOrDefault(barcode, 0) + 1);
}
PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
maxHeap.add(new int[]{entry.getValue(), entry.getKey()});
}
int prevFreq = 0, prevBarcode = -1;
int[] result = new int[barcodes.length];
int index = 0;
while (!maxHeap.isEmpty()) {
int[] entry = maxHeap.poll();
int freq = entry[0], barcode = entry[1];
result[index++] = barcode;
if (prevFreq > 0) {
maxHeap.add(new int[]{prevFreq, prevBarcode});
}
prevFreq = freq - 1;
prevBarcode = barcode;
}
return result;
}
}
Ставь 👍 и забирай 📚 Базу знаний
2 · 516 ·