共计 1584 个字符,预计需要花费 4 分钟才能阅读完成。
1054. 间隔相等的条形码
关键词:计数、哈希表
题目起源:1054. 间隔相等的条形码 – 力扣(Leetcode)
题目形容
T 计数 | |
T 哈希表 |
在一个仓库里,有一排条形码,其中第 i
个条形码为 barcodes[i]
。
请你重新排列这些条形码,使其中任意两个相邻的条形码不能相等。你能够返回任何满足该要求的答案,此题保障存在答案。
输出:barcodes = [1,1,1,2,2,2] | |
输入:[2,1,2,1,2,1] |
输出: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 |
优先队列
直观上来看,咱们应该尽可能把呈现次数多的放在后面,于是,可采纳优先队列来保护每个数呈现的次数,每次取出呈现次数最多的数放到排列开端,留神,每取出一个数,该数的呈现次数就须要 -1,当然,如果这个数与以后末尾数雷同,则以后必须换下一个数。
vector<int> rearrangeBarcodes(vector<int> &barcodes) { | |
// 统计各数呈现次数 | |
unordered_map<int, int> cnt; | |
for (auto &e: barcodes)cnt[e]++; | |
// 优先队列 | |
priority_queue<pair<int, int>> q; | |
for (const auto &[a, b]: cnt)q.emplace(b, a); | |
// 每次取出队头元素 | |
vector<int> res; | |
while (q.size()) {auto [xs, x] = q.top(); | |
q.pop(); | |
// 排列开端不是 x 则往开端放 x | |
if (res.empty() || res.back() != x) {res.push_back(x); | |
if (xs > 1)q.emplace(xs - 1, x); | |
} | |
// 如果开端是 x 则只能放其它数 | |
else { | |
// 题目保障有答案,所以到此处队列必然不为空 | |
auto [ys, y] = q.top(); | |
q.pop(); | |
res.push_back(y); | |
if (ys > 1)q.emplace(ys - 1, y); | |
// 把 x 放回去 | |
q.emplace(xs, x); | |
} | |
} | |
return res; | |
} |
工夫复杂度:O(nlog(n))
空间复杂度:O(n)
计数统计
通过后面剖析咱们发现,实际上,能够通过每隔一个地位放一个雷同数的操作来结构符合要求的排列。也即
- 第一个放数的地位是 0,第二个放数的地位是 2,以此类推,接着是 4、6、…,当下标越界时,回到地位 1,下一个放数的地位是 3,再下一个是 5,以此类推,接着是 7、8、9…。
- 数一批一批地放,值相等的数形成一批,至于先放值等于几的那一批并没有要求。
- 特地的,当 n 为奇数且有元素 x 呈现次数为 (n+1)/ 2 时,地位 0 必须是 x 的,此时 x 占有全副偶数地位,不然放不下。
vector<int> rearrangeBarcodes(vector<int> &barcodes) {int l = barcodes.size(); | |
if (l < 3)return barcodes; | |
// 统计各数呈现次数 | |
unordered_map<int, int> cnt; | |
for (auto &e: barcodes)cnt[e]++; | |
// 奇偶交替填充 | |
vector<int> res(l); | |
int even = 0, odd = 1, half = l / 2; | |
for (auto &[x, xs]: cnt) { | |
// 先填奇数地位 | |
// xs<=half 用于保障当 n 为奇数且元素 x 呈现次数为 (n+1)/ 2 时,x 肯定能放在所有偶数地位上 | |
while (xs > 0 && xs <= half && odd < l) | |
res[odd] = x, xs--, odd += 2; | |
// 再填偶数地位 | |
while (xs > 0) | |
res[even] = x, xs--, even += 2; | |
} | |
return res; | |
} |
工夫复杂度:O(n)
空间复杂度:O(n)
正文完