一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 327|回复: 2
收起左侧

[CareerCup] 移动链表元素和数组开销不一样吗》

[复制链接] |试试Instant~ |关注本帖
TonyJang 发表于 2014-9-23 20:06:49 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x

http://www.1point3acres.com/bbs/ ... &fromuid=107278

2.4 Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

原作者有句话说如果是数组那么开销会巨大,why?


wzf1943 发表于 2014-9-24 02:07:54 | 显示全部楼层
不是移动的开销,而是不断开辟新空间的开销。数组和链表在速度上的差距很小。甚至可以说没有。但是空间上,数组需要开辟连续的内存,但是链表是不需要的。
回复 支持 反对

使用道具 举报

eaglesky1990 发表于 2014-9-24 02:11:36 | 显示全部楼层
链表每次移动都是O(1)时间,但如果是数组的话你把后边一个元素移到前边需要把这之间的所有元素后移来腾地方,所以是O(n)的时间(如果要保持相对顺序的话是这样,如果无需保持,则像快排那样直接交换也可,那就是O(1))。所以数组开销会更大一些。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 12:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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