作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。
输入格式
- nums：一个整数数组，包含
0（红色）、1（白色）、2（蓝色）。
输出格式
- 不需要返回任何内容，需将
nums数组按上述规则排序。
示例
示例 1
输入: nums = [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]
示例 2
输入: nums = [2,0,1] 输出: [0,1,2]
方法一：计数排序
解题步骤
- 计数：遍历数组，计算
0、1和2的数量。 - 重写数组：根据各个数字的数量，重新填充数组。
完整的规范代码
def sortColors(nums): """ 使用计数排序对颜色进行排序 :param nums: List[int], 输入的整数数组，包含 0, 1, 2 代表不同颜色 """ count = {0: 0, 1: 0, 2: 0} for num in nums: count[num] += 1 index = 0 for color in range(3): for _ in range(count[color]): nums[index] = color index += 1 # 示例调用 nums = [2, 0, 2, 1, 1, 0] sortColors(nums) print(nums) # 输出: [0, 0, 1, 1, 2, 2]
算法分析
- 时间复杂度：(O(n))，其中
n是数组的长度。 - 空间复杂度：(O(1))，只使用了固定大小的额外空间。
方法二：一次遍历的荷兰国旗问题解法
解题步骤
- 初始化指针：设置三个指针，
low、mid和high分别用于追踪0的右边界和2的左边界，以及当前考虑的元素。 - 迭代处理元素：移动
mid指针，根据指向的值调整三个指针：
- 如果
nums[mid] == 0，交换nums[low]和nums[mid]，然后移动low和mid指针。 - 如果
nums[mid] == 1，只移动mid指针。 - 如果
nums[mid] == 2，交换nums[mid]和nums[high]，然后移动high指针。
完整的规范代码
def sortColors(nums): """ 使用荷兰国旗问题的解法一次遍历解决颜色排序问题 :param nums: List[int], 输入的整数数组，包含 0, 1, 2 代表不同颜色 """ low, mid, high = 0, 0, len(nums) - 1 while mid <= high: if nums[mid] == 0: nums[low], nums[mid] = nums[mid], nums[low] low += 1 mid += 1 elif nums[mid] == 1: mid += 1 else: nums[mid], nums[high] = nums[high], nums[mid] high -= 1 # 示例调用 nums = [2, 0, 1] sortColors(nums) print(nums) # 输出: [0, 1, 2]
算法分析
- 时间复杂度：(O(n))，只需要一次遍历。
- 空间复杂度：(O(1))，不使用额外空间。
方法三：双指针优化
解题步骤
- 双指针初始化：
left指向数组开头，right指向数组结尾。 - 双指针移动：遍历数组，使用
left和right两个指针分别处理0和2，保持1自然位于中间。
完整的规范代码
def sortColors(nums): """ 使用双指针优化解决颜色分类问题 :param nums: List[int], 输入的整数数组，包含 0, 1, 2 代表不同颜色 """ left, right = 0, len(nums) - 1 i = 0 while i <= right: if nums[i] == 0: nums[left], nums[i] = nums[i], nums[left] left += 1 i += 1 elif nums[i] == 2: nums[right], nums[i] = nums[i], nums[right] right -= 1 else: i += 1 # 示例调用 nums = [2, 0, 2, 1, 1, 0] sortColors(nums) print(nums) # 输出: [0, 0, 1, 1, 2, 2]
算法分析
- 时间复杂度：(O(n))，在最坏的情况下，数组需要被遍历两次。
- 空间复杂度：(O(1))，不需要额外空间。
方法四：简化的一次遍历
解题步骤
- 单次遍历：类似于荷兰国旗问题的解法，通过简化逻辑减少冗余操作。
- 直接交换：在遍历过程中，直接根据当前元素与
left和right指针的关系进行交换。
完整的规范代码
def sortColors(nums): """ 使用简化的一次遍历方法对颜色进行分类 :param nums: List[int], 输入的整数数组，包含 0, 1, 2 代表不同颜色 """ left, right = 0, len(nums) - 1 i = 0 while i <= right: while nums[i] == 2 and i < right: nums[i], nums[right] = nums[right], nums[i] right -= 1 while nums[i] == 0 and i > left: nums[i], nums[left] = nums[left], nums[i] left += 1 i += 1 # 示例调用 nums = [2, 0, 1] sortColors(nums) print(nums) # 输出: [0, 1, 2]
算法分析
- 时间复杂度：(O(n))，尽管存在嵌套循环，但每个元素最多被交换两次。
- 空间复杂度：(O(1))，使用常数额外空间。
方法五：内置函数优化
解题步骤
- 计数：使用 Python 内置函数统计
0、1、2的个数。 - 重构数组：根据统计结果重构原数组。
完整的规范代码
def sortColors(nums): """ 使用内置函数统计并重构数组 :param nums: List[int], 输入的整数数组，包含 0, 1, 2 代表不同颜色 """ count = [0] * 3 for num in nums: count[num] += 1 index = 0 for color in range(3): for _ in range(count[color]): nums[index] = color index += 1 # 示例调用 nums = [2, 0, 1] sortColors(nums) print(nums) # 输出: [0, 1, 2]
算法分析
- 时间复杂度：(O(n))，需要两次遍历数组，一次计数，一次重构。
- 空间复杂度：(O(1))，使用了有限的额外空间。
不同算法的优劣势对比
| 特征 | 方法一：计数排序 | 方法二：荷兰国旗问题 | 方法三：双指针优化 | 方法四：简化一次遍历 | 方法五：内置函数优化 |
| 时间复杂度 | (O(n)) | (O(n)) | (O(n)) | (O(n)) | (O(n)) |
| 空间复杂度 | (O(1)) | (O(1)) | (O(1)) | (O(1)) | (O(1)) |
| 优势 | 易于实现 | 单次遍历 | 降低遍历次数 | 高效处理 | 简洁，利用内置优化 |
| 劣势 | 两次遍历 | 需要掌握指针逻辑 | 较复杂的指针移动 | 潜在的多次交换 | 依赖于语言特性 |
应用示例
数据科学：在数据预处理阶段，快速分类和标记数据是常见需求，这些方法可以快速实现。
软件开发：在用户界面开发中，可能需要对大量颜色标签进行排序，以便更快地访问和渲染。
算法竞赛：在算法竞赛中，这些方法可以用来快速解决与分类和排序相关的问题，是提高效率的关键。欢迎关注微信公众号 数据分析螺丝钉
