找回密码
 立即注册

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的。
3 f" E* f7 E% H$ Z

0 ^. R( f" d" h) {# w! F! \考虑用insertion sort.
6 U, V$ D2 D# j6 X5 V先数个数,再根据coutner来覆盖。这样虽然是O(2N) time,但也算Linear,而且只用了3个counter, O(1) space, 一次swap都没有。 " q. Q$ Q) ]# o( x" y0 f

. d: l0 q7 u" f2 X如果要1-pass的话,而且不能swap的话,只有O(N) space的做法了。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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