y***e
发帖数: 32 | 1 给一个array长度为n。其中随机放了n1个红色，n2个绿色和n3个蓝色的球（n1 + n2 +
n3 = n）。设计一个算法排序这个array使得红球在所有绿球的前面，蓝球在所有绿球
的后面。
条件1是访问array里的球只能做一次颜色查询，例如访问到球array[i]时，只能查询球
array[i]一次。这个球可以和其他位置的球任意交换位置。
条件2是memory是O(1) |
h**6
发帖数: 4160 | 2 三个指针i,j,k，分别指向0, n1, n1+n2
如果i是红的，i后移；
如果i是绿的，ij交换，j后移；
如果i是蓝的，ik交换，k后移。
如果i到头了，jk还没到，继续jk交换后移。 |
l*****a
发帖数: 14598 | 3 不给你n1,n2呢
【在 h**6 的大作中提到】
: 三个指针i,j,k，分别指向0, n1, n1+n2
: 如果i是红的，i后移；
: 如果i是绿的，ij交换，j后移；
: 如果i是蓝的，ik交换，k后移。
: 如果i到头了，jk还没到，继续jk交换后移。
|
a**********0
发帖数: 422 | |
l*********8
发帖数: 4642 | 5 dutch flag problem?
+
【在 y***e 的大作中提到】
: 给一个array长度为n。其中随机放了n1个红色，n2个绿色和n3个蓝色的球（n1 + n2 +
: n3 = n）。设计一个算法排序这个array使得红球在所有绿球的前面，蓝球在所有绿球
: 的后面。
: 条件1是访问array里的球只能做一次颜色查询，例如访问到球array[i]时，只能查询球
: array[i]一次。这个球可以和其他位置的球任意交换位置。
: 条件2是memory是O(1)
|
l*****a
发帖数: 14598 | 6 又会有人夸你牛了 :)
【在 l*********8 的大作中提到】
: dutch flag problem?
:
: +
|
l*********8
发帖数: 4642 | 7 不敢当啊。 appentice都说了是leetcode原题。 我刚才看了一下是sort color.
【在 l*****a 的大作中提到】
: 又会有人夸你牛了 :)
|
m*****n
发帖数: 2152 | 8 leetcode原题，当时好像用了2前2后，4个index，从两边向中间扫。
+
【在 y***e 的大作中提到】
: 给一个array长度为n。其中随机放了n1个红色，n2个绿色和n3个蓝色的球（n1 + n2 +
: n3 = n）。设计一个算法排序这个array使得红球在所有绿球的前面，蓝球在所有绿球
: 的后面。
: 条件1是访问array里的球只能做一次颜色查询，例如访问到球array[i]时，只能查询球
: array[i]一次。这个球可以和其他位置的球任意交换位置。
: 条件2是memory是O(1)
|
l*****a
发帖数: 14598 | 9 前后两个就可以了
【在 m*****n 的大作中提到】
: leetcode原题，当时好像用了2前2后，4个index，从两边向中间扫。
:
: +
|
