几道百度笔试题
这几道题可能不少人已经见过，但有些题网上还没有见到非常完美的答案。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<R_2<...<R_M以及R_{M+1}<R_{M+2}<...R_N. 设计一个算法或编写一个程序，将文件中的记录排序为R_1'<R_2'<...<R_N',算法或程序读写文件的次数为O(N)，空间复杂度为O(1)，(亦即，你使用的内存大小和M,N均无关。)
3. 现有一数组{a_n}满足a_1<a_2<...<a_m, a_{m+1}<a_{m+2}<...<a_n，与上题不同的是m是未知的，设计算法快速的查找b是否在数组中。
4. 对于n*n的矩阵，每一行与每一列都是递增序列，例如：
$ [(1,3,4,7),(2,4,6,8),(3,5,7,9),(7,8,9,10)]$，
设计一个高效的算法查找任意一个给定的数字n是否在矩阵中。 好奇怪，为何数字矩阵显示不了 好奇怪，为何数字矩阵显示不了
sir_chen 发表于 2011-10-14 15:08 http://bbs.emath.ac.cn/images/common/back.gif
不知为何，偶尔会出现标签不自动转换成公式标记的问题。:L
注：我刚才将主题帖编辑了下，就不存在 2# 说的问题了。 为何都没人回答呢，高手何在 第4题n*n中找数N，以下是个高效的算法：
第一步 从第一列找值不大于N的最大数a，若其等于N，则结束。
第二步 从a右边相邻一列中往上找值不大于N的最大数b，若等于N，则结束。
第三步 将第二步找到的数b作为a，重复第二步的过程，直至进行到最后一列。
仍没找到，则所有的数中不存在N。 第一题，先搜索一遍，找到正数的个数，然后，在过一遍就可以了。
第二题，是将两队有序数排成一队的过程。
第三题，先搜索一遍，找到减少的那个数，然后两次二分法。 只会第四题,思路大概是这样的。
rowStart，搜索的开始行，
rowEnd，搜索的结束行，
那俩参数类似
void search(int** a,int rowStart,int rowEnd,int colStart,int colEnd,int toSearch,int* row,int* col)
{
while(rowStart<rowEnd && colStart <colEnd)
{
int midRow=(rowStart+rowEnd)/2;
int midCol=(colStart+colEnd)/2;
if(a == toSearch)
{
*row=midRow;
*col=midCol;
return ;
}
else
{
if(a < toSearch)
{
rowStart=midRow;
colStart=midCol;
}
else
{
if(toSearch > a)
{
rowStart=midRow;
colEnd=midCol;
}
else
{
if(toSearch < a)
{
rowEnd=midRow;
colStart= midCol;
}
else
{
rowEnd=midRow;
colEnd=midCol;
}
}
}
}
}
if(rowStart == rowEnd && colStart == colEnd)
{
*row=-1;
*col=-1;
return ;
}
else
{
if(rowStart == rowEnd)
{
二分搜索列;
}
else
{
二分搜索行;
}
}
} 第一题只需扫描一遍，不用两遍。
可以使用快速排序里面的二分的方法。只需一遍 关于第二题的描述，我怎么没看懂，可以重新说一遍吗 8# sheldenwade
页:
[1]
2