sir_chen 发表于 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<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:09

好奇怪,为何数字矩阵显示不了

gxqcn 发表于 2011-10-14 16:23:08

好奇怪,为何数字矩阵显示不了
sir_chen 发表于 2011-10-14 15:08 http://bbs.emath.ac.cn/images/common/back.gif

不知为何,偶尔会出现标签不自动转换成公式标记的问题。:L

注:我刚才将主题帖编辑了下,就不存在 2# 说的问题了。

sir_chen 发表于 2011-10-17 14:29:23

为何都没人回答呢,高手何在

056254628 发表于 2011-10-17 23:47:09

第4题n*n中找数N,以下是个高效的算法:
第一步 从第一列找值不大于N的最大数a,若其等于N,则结束。
第二步 从a右边相邻一列中往上找值不大于N的最大数b,若等于N,则结束。
第三步 将第二步找到的数b作为a,重复第二步的过程,直至进行到最后一列。
仍没找到,则所有的数中不存在N。

zgg___ 发表于 2011-10-18 11:10:09

第一题,先搜索一遍,找到正数的个数,然后,在过一遍就可以了。
第二题,是将两队有序数排成一队的过程。
第三题,先搜索一遍,找到减少的那个数,然后两次二分法。

sheldenwade 发表于 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<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
      {
            二分搜索行;
      }
    }

}

sheldenwade 发表于 2011-10-20 14:37:39

第一题只需扫描一遍,不用两遍。
可以使用快速排序里面的二分的方法。只需一遍

sheldenwade 发表于 2011-10-20 14:46:10

关于第二题的描述,我怎么没看懂,可以重新说一遍吗

kfroger 发表于 2011-10-26 10:58:11

8# sheldenwade
页: [1] 2
查看完整版本: 几道百度笔试题