几道百度笔试题

sir_chen

这几道题可能不少人已经见过，但有些题网上还没有见到非常完美的答案。

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

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

gxqcn

好奇怪，为何数字矩阵显示不了
sir_chen 发表于 2011-10-14 15:08

不知为何，偶尔会出现[TeX]标签不自动转换成公式标记的问题。

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

sir_chen

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

056254628

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

zgg___

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

sheldenwade

只会第四题,思路大概是这样的。
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[midRow][midCol] == toSearch)
        {
            *row=midRow;
            *col=midCol;
            return ;
        }
        else
        {
            if(a[midRow][midCol] < toSearch)
            {
                rowStart=midRow;
                colStart=midCol;
            }
            else
            {
                if(toSearch > 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
        {
            二分搜索行;
        }
    }

}

sheldenwade

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

sheldenwade

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

kfroger

8# sheldenwade