百度实习笔试题

只看该作者 · 2012-5-7 18:59

题目：

算法和程序设计二：数组al[0...mid-1]和al[mid...num-1]两个部分都已经分别排好序。要求合并使得整个数组al有序。请给出合并merge的代码。要求空间复杂度为O(1)。

我的想法的时间复杂度可能到了o(n^2)了，所以想求教大家的思路。

只看该作者 · 2012-5-7 19:12

定义两个游标，分别指向两段的未处理的数据，然后根据游标来插入数据，并且将第二段之前的数据进行后移一格。估计时间复杂度也很高。

只看该作者 · 2012-5-7 19:21

LS分析的很有道理，两个游标是肯定的，甚至需要第三个游标。
当后半部分有连续的数据插入到前半部分时，我觉得可能需要将前半部分的数据后移，这个后移时间复杂度就很高了。

只看该作者 · 2012-5-7 20:52

LZ还有没有更多的笔试试题

只看该作者 · 2012-5-8 16:35

不错不错，学习了，好东西。

只看该作者 · 2012-5-8 18:46

有没有完整的答案