Akamai店面一题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Akamai店面一题

Akamai店面一题# JobHunting - 待字闺中

y*e2014-06-20 07:06

1 楼

给一个array长度为n。其中随机放了n1个红色，n2个绿色和n3个蓝色的球（n1 + n2 +
n3 = n）。设计一个算法排序这个array使得红球在所有绿球的前面，蓝球在所有绿球
的后面。
条件1是访问array里的球只能做一次颜色查询，例如访问到球array[i]时，只能查询球
array[i]一次。这个球可以和其他位置的球任意交换位置。
条件2是memory是O(1)

h*62014-06-20 07:06

2 楼

三个指针i,j,k，分别指向0, n1, n1+n2
如果i是红的，i后移；
如果i是绿的，ij交换，j后移；
如果i是蓝的，ik交换，k后移。
如果i到头了，jk还没到，继续jk交换后移。

l*a2014-06-20 07:06

3 楼

不给你n1,n2呢

【在 h**6 的大作中提到】

: 三个指针i,j,k，分别指向0, n1, n1+n2
: 如果i是红的，i后移；
: 如果i是绿的，ij交换，j后移；
: 如果i是蓝的，ik交换，k后移。
: 如果i到头了，jk还没到，继续jk交换后移。

a*02014-06-20 07:06

4 楼

leetcode原题吗？

l*82014-06-20 07:06

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*a2014-06-20 07:06

6 楼

又会有人夸你牛了 :)

【在 l*********8 的大作中提到】

: dutch flag problem?
:
: +

l*82014-06-20 07:06

7 楼

不敢当啊。 appentice都说了是leetcode原题。我刚才看了一下是sort color.

【在 l*****a 的大作中提到】

: 又会有人夸你牛了 :)