几道百度笔试题

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

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

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

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

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

关于第二题的描述，我怎么没看懂，可以重新说一遍吗 sheldenwade 发表于 2011-10-20 14:46

这题是说存放在文件中的是两个有序数组，比如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)

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 几道百度笔试题