微软intern面经，求答案

回复 20# rayray81502

说实话 我面试时候就是这么答的 但是其实这是一个O（n^2)的程序 确实操作会小于n^2步，但是时间复杂度仍然是O（n^2)

怪我没有表述清楚，应该找一个O（nlgn）甚至更快的方案

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

回复 22# nkg114mc


    链表多出的那几个指针都要考虑空间吗。。。

回复 24# rayray81502

当然了，一个表项一个指针，这就是n个指针，如果可以的话，同样的空间我也可以再申一个n长度的数组，然后扫一遍原数组把每一项按要求的顺序存到新数组里，O(n)时间搞定，还用链表干嘛……

回复 24# rayray81502 [b][/b]


链表是要考虑的 因为链表的空间复杂度也是O(n)

quote]这不是版大发的100道题的原题吗？可以去编程区找到！
版大V587！
tsy3602 发表于 2012-3-13 20:11 [/quote]

能给个链接吗

啊, 不是吧, 这题我做过?????!!!!!
啊, 退步了, 哈哈

看半天才看明白, Divided and Conquer....
对于 ---- ++++ ---- ++++ 来说reverse中间那段"++++ ----" => "---- ++++"
然后再reverse两个小段, 一般递归log(n)的栈空间不算进去.

MS的一面居然问这个题, 太扯了.....

回复 29# wwwyhx

原来递归的栈空间是不算进去的