找回密码
 欢迎注册
查看: 43279|回复: 14

[讨论] 几道百度笔试题

[复制链接]
发表于 2011-10-14 14:53:00 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
这几道题可能不少人已经见过,但有些题网上还没有见到非常完美的答案。 1. 有一整数数列,其中包含正数和负数,现要求将正数全部排到右边,负数排在左边,并且保持各个正数之间和各个负数之间的相对位置不变。如:1,4,-3,5,-2,7,-6,排序后为:-3,-2,-6,1,4,5,7. 要求时间复杂度为O(n),空间为O(1) 2. 你现在有一个文件,文件中顺序存有N个记录,$R_1,R_2,...,R_N$,这些记录不是有序的,但是你知道一个整数M,这些记录满足$R_1
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-10-14 15:08:09 | 显示全部楼层
好奇怪,为何数字矩阵显示不了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-10-14 16:23:08 | 显示全部楼层
好奇怪,为何数字矩阵显示不了 sir_chen 发表于 2011-10-14 15:08
不知为何,偶尔会出现[TeX]标签不自动转换成公式标记的问题。 注:我刚才将主题帖编辑了下,就不存在 2# 说的问题了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-10-17 14:29:23 | 显示全部楼层
为何都没人回答呢,高手何在
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-10-17 23:47:09 | 显示全部楼层
第4题n*n中找数N,以下是个高效的算法: 第一步 从第一列找值不大于N的最大数a,若其等于N,则结束。 第二步 从a右边相邻一列中往上找值不大于N的最大数b,若等于N,则结束。 第三步 将第二步找到的数b作为a,重复第二步的过程,直至进行到最后一列。 仍没找到,则所有的数中不存在N。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-10-18 11:10:09 | 显示全部楼层
第一题,先搜索一遍,找到正数的个数,然后,在过一遍就可以了。 第二题,是将两队有序数排成一队的过程。 第三题,先搜索一遍,找到减少的那个数,然后两次二分法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-10-20 14:34:38 | 显示全部楼层
只会第四题,思路大概是这样的。 rowStart,搜索的开始行, rowEnd,搜索的结束行, 那俩参数类似 void search(int** a,int rowStart,int rowEnd,int colStart,int colEnd,int toSearch,int* row,int* col) { while(rowStart a[midRow][rowStart]) { rowStart=midRow; colEnd=midCol; } else { if(toSearch < a[midRow][rowEnd]) { rowEnd=midRow; colStart= midCol; } else { rowEnd=midRow; colEnd=midCol; } } } } } if(rowStart == rowEnd && colStart == colEnd) { *row=-1; *col=-1; return ; } else { if(rowStart == rowEnd) { 二分搜索列; } else { 二分搜索行; } } }
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-10-20 14:37:39 | 显示全部楼层
第一题只需扫描一遍,不用两遍。 可以使用快速排序里面的二分的方法。只需一遍
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-10-20 14:46:10 | 显示全部楼层
关于第二题的描述,我怎么没看懂,可以重新说一遍吗
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-10-26 10:58:11 | 显示全部楼层
8# sheldenwade
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-23 13:50 , Processed in 0.026103 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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