找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1312|回复: 5
收起左侧

[Amazon] A家遇到的一道数组排序题

[复制链接]

3

主题

2

精华

255

积分

高级会员

Rank: 3Rank: 3

积分
255
发表于 12-2-2014 10:18 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
要求: 输入一个数组(未排序),输出数组要保证每一个一个数字要比它左右相邻的数字都小或者都大,类似ABABAB的格式。
6 h% q) }! H2 X" w: b" ]我给出的解法是 先排序,然后swap相邻的数字,复杂度是nlogn。
( X" N$ Y! Q' J; V% u9 [  _面试官让找出O(n)解法 ,说是比较tricky,但不给提示,求问高手如何解?

0

主题

0

精华

232

积分

高级会员

Rank: 3Rank: 3

积分
232
发表于 12-3-2014 01:58 AM | 显示全部楼层
我抛个砖: " z. ^( G) C/ W# H: A- I) ~2 e& A
如果是每个值不相同的话:
( P1 J- d& o: H( B+ E. k9 Q3 m核心思想是先建个最小堆,O(n), 然后中序遍历。
3 B. T, H. k. @. N; E2 C4 I. |
1 n$ n7 e& l" v1 U! ^! |2 k1.如果是恰好奇数个节点,那么除了叶子外,每个节点恰好都有两个子节点,完美
. ]; i1 ^: {2 x2. 如果有偶数个节点,那么把最小的那个数先找出来拿出来,再把剩下的奇数节点建最小堆和中序遍历,那么剩下的那些中序遍历完肯定是"大小大小....大小大", 这时你把之前得到的最小那个数随便放在最左边或者最右边就可以了

84

主题

32

精华

1278

积分

顶级会员

Rank: 6Rank: 6

积分
1278

活跃会员热心会员最佳新人精华帖之王

发表于 12-3-2014 02:16 AM | 显示全部楼层
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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