找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

123
返回列表 发新帖
楼主: tc350981
收起左侧

[PureStorage] Pure Storage 两次onsite

[复制链接]

1

主题

1

精华

23

积分

新米人

Rank: 1

积分
23
发表于 6-22-2017 11:19 AM | 显示全部楼层
2. lc sort color 要求swap次数最少。那个经典的法国国旗算法不work,不能保证swap最少,最优解是on时间o1space,我没给出最优解,给出了on时间onspace的。
: S/ m6 Y$ D1 F6 A) ^3 n# P. x' L

" k9 A5 P6 @9 Y# }6 |考虑用insertion sort.
1 R9 a) l) i2 f: q先数个数,再根据coutner来覆盖。这样虽然是O(2N) time,但也算Linear,而且只用了3个counter, O(1) space, 一次swap都没有。
. b3 r+ V: f7 D  l' y0 [6 F" y3 r8 z1 |& v" {
如果要1-pass的话,而且不能swap的话,只有O(N) space的做法了。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表