首页 > 试题广场 >

排列颜色

[编程题]排列颜色
  • 热度指数:15788 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
现在有一个包含n个物体的数组,其中物体颜色为颜色为红色、白色或蓝色,请对这个数组进行排序,让相同颜色的物体相邻,颜色的顺序为红色,白色,蓝色。
我们用0,1,2分别代表颜色红,白,蓝
注意:
本题要求你不能使用排序库函数
扩展:
一个非常直接的解法是两步的计数排序的算法
首先:遍历一遍数组,记录0,1,2的数量,然后重写这个数组,先将0写入,再将1写入,再将2写入
你能给出一个只用一步,并且能在常数级空间复杂度解决这个问题的算法吗?
头像 去种田的程序员
发表于 2020-06-01 16:12:28
问题描述: 现在有一个包含n个物体的数组,其中物体颜色为颜色为红色、白色或蓝色,请对这个数组进行排序,让相同颜色的物体相邻,颜色的顺序为红色,白色,蓝色。 我们用0,1,2分别代表颜色红,白,蓝 注意: 本题要求你不能使用排序库函数 思路:三路快排的思想,以1作为 展开全文
头像 卫宫士郎红A
发表于 2020-07-17 11:22:58
题目描述 现在有一个包含n个物体的数组,其中物体颜色为颜色为红色、白色或蓝色,请对这个数组进行排序,让相同颜色的物体相邻,颜色的顺序为红色,白色,蓝色。 我们用0,1,2分别代表颜色红,白,蓝 注意: 本题要求你不能使用排序库函数 扩展: 一个非常直接的解法是两步的计数排序的算法 首先: 展开全文
头像 华科不平凡
发表于 2020-09-25 14:46:22
这个问题被称为荷兰国旗问题: 解题思路:利用三个指针p0, curr, p2,其中p0指向0的右边界,p2指向2的左边界,curr指向当前元素。整个过程确保了[0,p0)的区间都是1,(p2, n-1]的区间都是2。 完整过程: 将p0初始化为0,curr初始化为0,p2初始化为n-1 如果c 展开全文
头像 jing_zhong
发表于 2021-09-04 12:01:32
题目描述:现在有一个包含n个物体的数组,其中物体颜色为颜色为红色、白色或蓝色,请对这个数组进行排序,让相同颜色的物体相邻,颜色的顺序为红色,白色,蓝色。我们用0,1,2分别代表颜色红,白,蓝注意:本题要求你不能使用排序库函数思路:一个非常直接的解法是两步的计数排序的算法  &nb 展开全文
头像 勇敢牛牛,不怕困难!
发表于 2021-09-29 11:24:26
class Solution { public: void sortColors(int A[], int n) { int zeroPos = -1, twoPos = n, idx = 0; while (idx < twoPos) { if (A[idx] 展开全文