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

百度笔试题啊，求算法太伤心了
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 5int 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]时，同理。

想来想去，比树好实现些