百度笔考试题啊求算法太伤心了

百度笔试题啊，求算法太伤心了
1．给定如下的n*n的数字矩阵，每行从左到右是严格递增，每列的数据也是严格递增

1 2 3

3 5 6

4 8 9

现在要求设计一个算法，给定一个数k 判断出k是否在这个矩阵中。描述算法并且给出时间复杂度（不考虑载入矩阵的消耗）

2．设一个64位整型n,各个bit位是1的个数为a个. 比如7, 2进制就是 111, 所以a为3。

现在给出m个数, 求各个a的值。要求代码实现。

。。。不会啊

------解决方案--------------------
第一个不会；
第二个：

C/C++ code

#include<stdio.h>
#define M 5
int count=0;

int GetCnt(int n)
{
    
    count=0;    
    do{
        if( n&1)
        {
            count++;
        }
    }
    while( n>>=1 );

    return count;
}

int main(int argc,char * argv[])
{
    int test[M]={7,3,34,2,234};

    for(int i=0;i<M;++i)
    {
        printf("%d\n",GetCnt(test[i]) );
    }
    return 0;
}

------解决方案--------------------
第一个

C/C++ code



int fun(int k, int (*)a[])
{
  if (k < a[n-1][n-1])
    return 1;
  else 
    return 0;
}

------解决方案--------------------

C/C++ code


bool function (int k , int a[][n],int m)
{
    for (int i=0; i<m; i++)
        for (int j=0; j<n;j++)
        {
            if (k == a[i][j])
                return true;
            else
                continue;
        }
    return false;
}

------解决方案--------------------
第一个，我觉得用递归比较好。

首先找第一个哨兵：arry[N/2][N/2]与K判断。
1  2  3  4
3  5  6  7
4  8  9  10
5  11 12 13


K<arry[N/2][N/2]时，产生2个哨兵：arry[N/4][N/2]和arry[N/2][N/4]，继续判断，又转化为同样的问题。

K>arry[N/2][N/2]时，同理。

想来想去，比树好实现些

百度笔考试题啊求算法太伤心了

相关推荐