LeetCode 1054 Distant Barcodes 题解：Go 实现频次排序与交错重排

LeetCode 1054 Distant Barcodes 题解Go 实现频次排序与交错重排【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-GoDistant Barcodes相隔条形码是一道典型的重排数组使相邻元素互不相同问题与 LeetCode 767 Reorganize String 同源同法。本文基于 LeetCode-Go 仓库中该题的完整文档、Go 源码实现与测试用例详细拆解频次降序排序 双指针交错取数的解题思路并给出可直接复用的 Go 实现与复杂度分析。读完本文你将掌握这一类相邻不相等重排问题的通用解法以及仓库内该题代码的每一行设计意图。题目描述与题意题目原文来自 leetcode/1054.Distant-Barcodes/README.mdIn a warehouse, there is a row of barcodes, where thei-th barcode isbarcodes[i]. Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.中文题意在一个仓库里有一排条形码其中第i个条形码为barcodes[i]。请你重新排列这些条形码使其中两个相邻的条形码不能相等。你可以返回任何满足该要求的答案题目保证存在答案。题目给出两个示例示例 1: Input: [1,1,1,2,2,2] Output: [2,1,2,1,2,1] 示例 2: Input: [1,1,1,1,2,2,3,3] Output: [1,3,1,3,2,1,2,1]约束条件Note1 barcodes.length 100001 barcodes[i] 10000注意输出不唯一题目明确说明 You may return any answer因此示例输出只是众多合法答案中的一种只要任意两个相邻元素不相等即可。解题思路先按频次降序排序再交错取数文档中给出的解题思路非常精炼核心只有两条这一题和第 767 题原理完全一样而 767 Reorganize String 是 Google 的面试题先按照每个数字的频次从高到低进行排序注意会有频次相同的数字。排序以后分别从第 0 号位和中间的位置开始往后取数取完以后即为最终解。仓库根目录 README.md 的 Sorting 章节也把这两题归为一类Reordering so that no two adjacent elements are equal. Problems 767, 1054.这套思路之所以成立依赖一个关键前提——题目保证答案存在。对于长度为n的数组答案存在等价于出现次数最多的元素其频次不超过(n1)/2即ceil(n/2)。这个限制保证了频次降序排序后相同元素被压缩在一段连续区间内且该区间长度不超过数组的一半从而可以通过前半段 后半段交错的方式把相同元素彻底隔开。具体流程如下统计每个数字的出现频次按频次从高到低对元素做稳定排列频次相同的元素聚在一起设排序后数组长度为n取j (n-1)/2 1即中间位置之后的第一个下标指针i从0遍历到(n-1)/2依次将bfs[i]与bfs[j]交替放入结果数组直到j越界。由于频次最高的元素只出现在排序数组的前半段而交错取数保证相邻位置分别来自前半段与后半段因此任何两个相邻位置都不会取到相同的元素。源码精读两个函数的完整实现仓库中本题的实现位于 leetcode/1054.Distant-Barcodes/1054. Distant Barcodes.go由两个函数组成入口函数rearrangeBarcodes和辅助函数barcodesFrequencySort。入口函数 rearrangeBarcodesfunc rearrangeBarcodes(barcodes []int) []int { bfs : barcodesFrequencySort(barcodes) if len(bfs) 0 { return []int{} } res : []int{} j : (len(bfs)-1)/2 1 for i : 0; i (len(bfs)-1)/2; i { res append(res, bfs[i]) if j len(bfs) { res append(res, bfs[j]) } j } return res }逐行解读第 6 行先调用barcodesFrequencySort得到频次降序排列的数组bfs第 79 行空输入直接返回空切片保证函数健壮性第 11 行计算交错起点j (len(bfs)-1)/2 1。这是整个算法的关键——(len(bfs)-1)/2是前半段的最后一个下标j从后半段第一个元素开始第 1218 行i从0走到前半段末尾每轮先取bfs[i]若j尚未越界再取bfs[j]形成前半段元素、后半段元素、前半段元素、后半段元素……的交错序列。数组长度为奇数时最后一个元素恰好是前半段的最后一个元素此时j已越界不进入 if 分支。频次排序函数 barcodesFrequencySortfunc barcodesFrequencySort(s []int) []int { if len(s) 0 { return []int{} } sMap : map[int]int{} // 统计每个数字出现的频次 cMap : map[int][]int{} // 按照频次作为 key 排序 for _, b : range s { sMap[b] } for key, value : range sMap { cMap[value] append(cMap[value], key) } var keys []int for k : range cMap { keys append(keys, k) } sort.Sort(sort.Reverse(sort.IntSlice(keys))) res : make([]int, 0) for _, k : range keys { for i : 0; i len(cMap[k]); i { for j : 0; j k; j { res append(res, cMap[k][i]) } } } return res }这个辅助函数用两级 map 桶排序的方式实现了按频次降序重排与 767 题中的frequencySort767见 leetcode/0767.Reorganize-String/767. Reorganize String.go结构一致只是把byte换成了int。要点如下sMap统计频次遍历输入sMap[b]记录每个数字出现的次数cMap以频次为桶cMap[value] append(cMap[value], key)把拥有相同频次的数字归入同一个桶对频次 key 降序排序收集所有频次到keys用sort.Sort(sort.Reverse(sort.IntSlice(keys)))实现降序按桶展开外层循环从高频次到低频次中层循环遍历该频次桶内的每个数字内层循环把该数字重复k次追加进结果最终得到频次高的元素在前、相同元素连续排列的数组。这里有一个值得注意的实现细节cMap内同一频次桶中多个数字的先后顺序取决于Go map 的随机迭代顺序因此展开结果并不唯一。例如示例 2 中数字2和3频次相同桶内顺序既可能是[2,3]也可能是[3,2]最终交错出的合法答案也可能与题目示例不同——这完全符合题目 You may return any answer 的要求只要相邻元素不相等即为正确。正确性为什么交错取数能保证相邻不等把barcodesFrequencySort的输出记为bfs它满足两个性质相同元素连续相同的数字在bfs中一定聚成一个连续区间最长连续区间的长度 ≤ (n1)/2因为题目保证答案存在频次最高的元素出现次数不超过ceil(n/2)。当i从0到(n-1)/2、j从(n-1)/21到n-1交错取数时最终数组的相邻位置一个来自bfs前半段、一个来自bfs后半段。由于同一元素的连续区间最多覆盖前半段或后半段的一半不会同时跨越两段中的相邻位置任何相邻两个位置都不可能取到同一个数字。这正是 767 / 1054 这类相邻不相等重排问题的通用骨架。复杂度分析设输入数组长度为n不同数字个数为m不同频次档位数为k时间复杂度频次统计为O(n)对频次 key 排序为O(k log k)k不超过m展开结果为O(n)。整体为O(n log n)量级实际排序的只是频次档位集合规模远小于n空间复杂度sMap、cMap与结果数组合计为O(n)。测试用例验证仓库配套的测试文件 leetcode/1054.Distant-Barcodes/1054. Distant Barcodes_test.go 覆盖了三组输入qs : []question1054{ {para1054{[]int{1, 1, 1, 2, 2, 2}}, ans1054{[]int{2, 1, 2, 1, 2, 1}}}, {para1054{[]int{1, 1, 1, 1, 2, 2, 3, 3}}, ans1054{[]int{1, 3, 1, 3, 2, 1, 2, 1}}}, {para1054{[]int{}}, ans1054{[]int{}}}, }分别对应题目给出的两个官方示例以及一个空输入边界用例。该测试以打印方式运行函数并输出【input】与【output】可直接在仓库中执行验证。关联题目与扩展阅读本题与 LeetCode 767 Reorganize String 是同一类问题仓库中 767 题的解法源码与测试位于 leetcode/0767.Reorganize-String/其中frequencySort767还额外包含可行性检查一旦某个字符频次超过(len(sb)1)/2立即返回空串因为此时不存在合法重排本题因题目保证答案存在而省略了该检查。两题对照阅读可以完整掌握可行性判断 频次排序 交错取数的解题闭环。此外仓库根目录 README.md 的 Sorting 章节Reordering so that no two adjacent elements are equal. Problems 767, 1054与 topic 目录下的主题导图将本题归类在排序大类之下适合作为刷题路线图参考。小结Distant Barcodes 的解法可以提炼为三步统计频次 → 按频次降序重排相同元素聚拢→ 从第 0 位与中间位交错取数。借助题目保证存在答案的前提这一构造性算法能够在线性展开 小规模排序的开销内完成重排是相邻元素不相等类问题的标准范式。仓库中的 Go 实现 与 测试用例 可直接运行、对照验证也可作为后续刷题时的模板参考。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考