kfroger 发表于 2011-10-26 10:59:51

8# sheldenwade

一般的快排不行，要求负数原来的顺序不能打乱

sir_chen 发表于 2011-12-8 10:39:12

快排显然不行的，要求空间复杂度为O(1)，要是不考虑空间复杂度，那是相当简单的：申请一个同样大小的数组b，扫描一遍得到负数个数m，然后扫描第二遍，遇到负数就从b往后放，遇到正数就从b往后放，这样时间是O(n)，但是空间也是O(n)

sir_chen 发表于 2011-12-8 10:48:30

关于第二题的描述，我怎么没看懂，可以重新说一遍吗
sheldenwade 发表于 2011-10-20 14:46 http://bbs.emath.ac.cn/images/common/back.gif
这题是说存放在文件中的是两个有序数组，比如1,2,3,4,3,5,6,7,8,9，这里M=4，整个数组不一定有序，但是从1到M和M+1到N都是有序的。

kfroger 发表于 2011-12-8 11:03:38

12# sir_chen
如果单就快排，其实也有空间复杂度为O(1)的

wayne 发表于 2011-12-19 00:18:44

第一题用基本的选择排序，时间复杂为O(n)空间复杂度为O(1)
页: 1 [2]
查看完整版本: 几道百度笔试题