LeetCode-Go 题解75. Sort Colors 荷兰国旗问题的三种 Go 实现一次遍历游标法 / 计数排序 / 三路快排【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读75. Sort Colors颜色分类是 LeetCode 上一道经典的原地排序题目数组元素只有0、1、2三类要求不使用库函数sort、在原地完成排序。本文以 leetcode/0075.Sort-Colors/README.md 为核心脉络结合 LeetCode-Go 仓库中 75. Sort Colors.go 的实际实现与其测试用例系统讲解一次遍历游标法、计数排序、三路快排三种解法并给出复杂度对比与可复现的运行验证方式。读完后你不仅能 AC 本题还能举一反三理解荷兰国旗问题这一快排分区思想的源头。题目回顾把 0、1、2 排成三段原题描述如下Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.即数组中的0代表红色、1代表白色、2代表蓝色要求原地排序使同色相邻、整体顺序为红 → 白 → 蓝。题目明确不允许调用库的排序函数。一个官方示例Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2]题目末尾的 Follow up 提出了更高的要求比较直接的思路是两遍扫描的计数排序第一遍统计0、1、2的个数第二遍按个数依次覆写数组更进一步能否设计出一趟扫描、只使用常数级额外空间的算法如文档题目大意所言这道题的抽象题意其实就是排序因此用快排思想一次通过也是完全可行的。解法一一次遍历游标法仓库实际实现针对 Follow up一次循环 常数空间的要求文档给出的核心思路是由于数字只会出现0、1、2三个值用游标移动控制写入顺序即可。具体逻辑是0排在最前面每添加一个0就需要顺势往后放置1和21排在2前面添加1时也要往后再放一个2至于2只需移动遍历游标。LeetCode-Go 仓库中 75. Sort Colors.go 正是这一思路的直接落地package leetcode func sortColors(nums []int) { zero, one : 0, 0 for i, n : range nums { nums[i] 2 if n 1 { nums[one] 1 one } if n 0 { nums[zero] 0 zero } } }逐行推演三个覆盖位的联动这里的两个指针含义非常精妙zero下一个0应写入的位置也是已排好0段的末尾one下一个1应写入的位置也是已排好0、1段的末尾。每遍历到一个元素n都先无条件把当前位置覆写为2把未知区当作2占位然后根据n的取值依次向前覆盖先写2nums[i] 2保证当前位置最终归属蓝段n 1时写1把one指向的位置写成1并前进one。由于新来的元素是0或1它要么替换掉刚才多写的2元素为1时要么为下一步的0腾位置元素为0时n 0时写0把zero指向的位置写成0并前进zero。因为zero始终不超过one所以写0时要么覆盖掉刚写的1要么覆盖掉最初写的2永远不会破坏已排好的前缀。以输入[2,0,2,1,1,0]为例走一遍in写入序列nums[i]2 后按序覆盖zeroone02[2]0010[0,2,2]1122[0,2,2]1131[0,1,2,2]1241[0,1,1,2,2]1350[0,0,1,1,2,2]24最终输出[0,0,1,1,2,2]与题目示例完全一致。该实现一趟遍历完成排序时间 O(n)、空间 O(1)且不借助任何额外数组满足 Follow up 的全部约束。测试用例验证仓库同目录下的 75. Sort Colors_test.go 通过表驱动测试覆盖了多个输入形态空数组[]→[]单元素[1]→[1]官方示例[2,0,2,1,1,0]→[0,0,1,1,2,2]长序列[2,0,1,1,2,0,2,1,2,0,0,0,1,2,2,2,0,1,1]→[0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,2]。长用例特别验证了大量元素交错出现时游标覆盖逻辑仍能保证三段严格有序覆盖了空输入、退化输入与常规输入的边界情况。解法二两遍扫描的计数排序文档明确指出这道题可以用计数排序适合待排序数字很少的题目。思路是用一个容量为 3 的计数数组第一遍统计0、1、2各自出现的次数第二遍按先0后1再2的顺序把数组覆写回去。func sortColorsCounting(nums []int) { cnt : [3]int{} for _, n : range nums { cnt[n] } idx : 0 for v : 0; v 2; v { for ; cnt[v] 0; cnt[v]-- { nums[idx] v idx } } }时间复杂度 O(n)两遍线性扫描空间复杂度 O(K)其中K 3是取值种类的个数文档特别标注了这一题 K 3。当待排序数字的取值域远小于元素个数时计数排序在常数因子和可读性上都极具优势本题恰好只有三种取值计数数组小到可以退化为三个局部变量。解法三三路快排荷兰国旗问题的经典解法文档最后补充这道题也可以用一次三路快排。数组分为 3 部分第一个部分都是 0中间部分都是 1最后部分都是 2。三路快排Dutch National Flag迪杰斯特拉提出的荷兰国旗问题用三个指针维护三段边界func sortColors3Way(nums []int) { lo, hi, i : 0, len(nums)-1, 0 for i hi { switch nums[i] { case 0: nums[lo], nums[i] nums[i], nums[lo] lo i case 1: i case 2: nums[i], nums[hi] nums[hi], nums[i] hi-- } } }lo0段的右边界nums[:lo]全为0i当前扫描位置1直接跳过hi2段的左边界nums[hi1:]全为2。遇到2时与hi交换后不推进i因为换回来的元素可能还是2需要再次判断遇到0时与lo交换后i前进因为换回来的元素只可能是1。同样一趟完成时间 O(n)、空间 O(1)。这种三段分区的思想在仓库其他题目中也有体现例如 215. Kth Largest Element in an Array.go 中的partition函数就是快排分区的工程化应用配合随机化基准值把期望复杂度稳定在 O(n)两者互相印证三路分区是快排递归树中处理重复元素的基石。三种解法对比解法扫描次数时间复杂度空间复杂度特点一次遍历游标法仓库实现1O(n)O(1)代码最简覆盖式写入满足 Follow up计数排序2O(n)O(K)本题 K3思路直白适合取值域小的场景三路快排荷兰国旗1O(n)O(1)分区思想通用是快排处理重复值的原型三种解法的共同前提是元素取值只有 0、1、2 三种因此三段式的线性算法成为可能这也是为什么题目要特意禁止调用库排序函数——那会掩盖题目真正想考察的分区思想。在仓库中运行与验证仓库采用package leetcode统一组织所有题解本题目录 leetcode/0075.Sort-Colors 下包含解法文件、测试文件和本文对应的 README。本地验证方式# 运行该题单测含 -v 输出便于观察输入输出 go test -v ./leetcode/0075.Sort-Colors/ -run Test_Problem75 # 或者运行全部 leetcode 包测试并生成覆盖率文件 go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...第二条命令与仓库根目录 gotest.sh 的脚本逻辑一致也是该项目生成 coverage.txt 覆盖率文件的标准方式go.mod 声明了模块github.com/halfrost/LeetCode-Go与 Go 1.19 版本要求并通过对structures、template等子模块的replace指令完成本地依赖管理。小结75. Sort Colors是一道一题三解的高频面试题计数排序考察对取值域有限的洞察一次遍历游标法考察原地覆写与指针联动的设计能力三路快排则直指荷兰国旗问题的分区本质。LeetCode-Go 仓库选用游标法作为主解正是因为它以最少的代码同时满足了一趟扫描 常数空间的全部约束理解这段实现等于同时掌握了后续 Kth Largest、快排随机化等题目的底层思维。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 题解75. Sort Colors 荷兰国旗问题的三种 Go 实现一次遍历游标法 / 计数排序 / 三路快排【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读75. Sort Colors颜色分类是 LeetCode 上一道经典的原地排序题目数组元素只有0、1、2三类要求不使用库函数sort、在原地完成排序。本文以 leetcode/0075.Sort-Colors/README.md 为核心脉络结合 LeetCode-Go 仓库中 75. Sort Colors.go 的实际实现与其测试用例系统讲解一次遍历游标法、计数排序、三路快排三种解法并给出复杂度对比与可复现的运行验证方式。读完后你不仅能 AC 本题还能举一反三理解荷兰国旗问题这一快排分区思想的源头。题目回顾把 0、1、2 排成三段原题描述如下Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.即数组中的0代表红色、1代表白色、2代表蓝色要求原地排序使同色相邻、整体顺序为红 → 白 → 蓝。题目明确不允许调用库的排序函数。一个官方示例Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2]题目末尾的 Follow up 提出了更高的要求比较直接的思路是两遍扫描的计数排序第一遍统计0、1、2的个数第二遍按个数依次覆写数组更进一步能否设计出一趟扫描、只使用常数级额外空间的算法如文档题目大意所言这道题的抽象题意其实就是排序因此用快排思想一次通过也是完全可行的。解法一一次遍历游标法仓库实际实现针对 Follow up一次循环 常数空间的要求文档给出的核心思路是由于数字只会出现0、1、2三个值用游标移动控制写入顺序即可。具体逻辑是0排在最前面每添加一个0就需要顺势往后放置1和21排在2前面添加1时也要往后再放一个2至于2只需移动遍历游标。LeetCode-Go 仓库中 75. Sort Colors.go 正是这一思路的直接落地package leetcode func sortColors(nums []int) { zero, one : 0, 0 for i, n : range nums { nums[i] 2 if n 1 { nums[one] 1 one } if n 0 { nums[zero] 0 zero } } }逐行推演三个覆盖位的联动这里的两个指针含义非常精妙zero下一个0应写入的位置也是已排好0段的末尾one下一个1应写入的位置也是已排好0、1段的末尾。每遍历到一个元素n都先无条件把当前位置覆写为2把未知区当作2占位然后根据n的取值依次向前覆盖先写2nums[i] 2保证当前位置最终归属蓝段n 1时写1把one指向的位置写成1并前进one。由于新来的元素是0或1它要么替换掉刚才多写的2元素为1时要么为下一步的0腾位置元素为0时n 0时写0把zero指向的位置写成0并前进zero。因为zero始终不超过one所以写0时要么覆盖掉刚写的1要么覆盖掉最初写的2永远不会破坏已排好的前缀。以输入[2,0,2,1,1,0]为例走一遍in写入序列nums[i]2 后按序覆盖zeroone02[2]0010[0,2,2]1122[0,2,2]1131[0,1,2,2]1241[0,1,1,2,2]1350[0,0,1,1,2,2]24最终输出[0,0,1,1,2,2]与题目示例完全一致。该实现一趟遍历完成排序时间 O(n)、空间 O(1)且不借助任何额外数组满足 Follow up 的全部约束。测试用例验证仓库同目录下的 75. Sort Colors_test.go 通过表驱动测试覆盖了多个输入形态空数组[]→[]单元素[1]→[1]官方示例[2,0,2,1,1,0]→[0,0,1,1,2,2]长序列[2,0,1,1,2,0,2,1,2,0,0,0,1,2,2,2,0,1,1]→[0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,2]。长用例特别验证了大量元素交错出现时游标覆盖逻辑仍能保证三段严格有序覆盖了空输入、退化输入与常规输入的边界情况。解法二两遍扫描的计数排序文档明确指出这道题可以用计数排序适合待排序数字很少的题目。思路是用一个容量为 3 的计数数组第一遍统计0、1、2各自出现的次数第二遍按先0后1再2的顺序把数组覆写回去。func sortColorsCounting(nums []int) { cnt : [3]int{} for _, n : range nums { cnt[n] } idx : 0 for v : 0; v 2; v { for ; cnt[v] 0; cnt[v]-- { nums[idx] v idx } } }时间复杂度 O(n)两遍线性扫描空间复杂度 O(K)其中K 3是取值种类的个数文档特别标注了这一题 K 3。当待排序数字的取值域远小于元素个数时计数排序在常数因子和可读性上都极具优势本题恰好只有三种取值计数数组小到可以退化为三个局部变量。解法三三路快排荷兰国旗问题的经典解法文档最后补充这道题也可以用一次三路快排。数组分为 3 部分第一个部分都是 0中间部分都是 1最后部分都是 2。三路快排Dutch National Flag迪杰斯特拉提出的荷兰国旗问题用三个指针维护三段边界func sortColors3Way(nums []int) { lo, hi, i : 0, len(nums)-1, 0 for i hi { switch nums[i] { case 0: nums[lo], nums[i] nums[i], nums[lo] lo i case 1: i case 2: nums[i], nums[hi] nums[hi], nums[i] hi-- } } }lo0段的右边界nums[:lo]全为0i当前扫描位置1直接跳过hi2段的左边界nums[hi1:]全为2。遇到2时与hi交换后不推进i因为换回来的元素可能还是2需要再次判断遇到0时与lo交换后i前进因为换回来的元素只可能是1。同样一趟完成时间 O(n)、空间 O(1)。这种三段分区的思想在仓库其他题目中也有体现例如 215. Kth Largest Element in an Array.go 中的partition函数就是快排分区的工程化应用配合随机化基准值把期望复杂度稳定在 O(n)两者互相印证三路分区是快排递归树中处理重复元素的基石。三种解法对比解法扫描次数时间复杂度空间复杂度特点一次遍历游标法仓库实现1O(n)O(1)代码最简覆盖式写入满足 Follow up计数排序2O(n)O(K)本题 K3思路直白适合取值域小的场景三路快排荷兰国旗1O(n)O(1)分区思想通用是快排处理重复值的原型三种解法的共同前提是元素取值只有 0、1、2 三种因此三段式的线性算法成为可能这也是为什么题目要特意禁止调用库排序函数——那会掩盖题目真正想考察的分区思想。在仓库中运行与验证仓库采用package leetcode统一组织所有题解本题目录 leetcode/0075.Sort-Colors 下包含解法文件、测试文件和本文对应的 README。本地验证方式# 运行该题单测含 -v 输出便于观察输入输出 go test -v ./leetcode/0075.Sort-Colors/ -run Test_Problem75 # 或者运行全部 leetcode 包测试并生成覆盖率文件 go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...第二条命令与仓库根目录 gotest.sh 的脚本逻辑一致也是该项目生成 coverage.txt 覆盖率文件的标准方式go.mod 声明了模块github.com/halfrost/LeetCode-Go与 Go 1.19 版本要求并通过对structures、template等子模块的replace指令完成本地依赖管理。小结75. Sort Colors是一道一题三解的高频面试题计数排序考察对取值域有限的洞察一次遍历游标法考察原地覆写与指针联动的设计能力三路快排则直指荷兰国旗问题的分区本质。LeetCode-Go 仓库选用游标法作为主解正是因为它以最少的代码同时满足了一趟扫描 常数空间的全部约束理解这段实现等于同时掌握了后续 Kth Largest、快排随机化等题目的底层思维。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
