1.赋值运算符函数
4.替换空格

3.二维数组中的查找

Author posted @ 2013年9月30日 17:43 in 剑指Offer with tags c++ , 1772 阅读

给一个有规律的整数矩阵,每行元素从左到右递增,第列元素从上到下递增。

要求完成一个查找函数,输入为满足以上条件的一个二维数组以及一个整数,判断数组中是否包含此整数。

如:

[tex] \begin{bmatrix}  1 & 2 & 8 & 9 \\ 2 & 4& 9& 12\\ 4 & 7 & 10&13 \\ 6 & 8 & 11& 15\end{bmatrix}[/tex]

查找7应当返回true,查找5应当返回false.

因为 只要求找到,不要求统计出现次数,而且此数组有规律,不用遍历用divide and conquer来做

我的习惯是用STL,但对于这个简单例子,用数组显然更高效,书中用的指针,看起来更高端了。

书中的解释很清楚。用指针访问数组元素应该是这样:

假如给定一个N-by-M的二维数组A,那么*A 指向第一个元素即A[0][0], 因为所有元素都先从行再到列地按顺序存储在内存中,所以第i行第j列的元素A[i][j]在内存中的位置是A[i*M+j]

书中从右上到左下查找,我稍微改了下,从左下到右上查找:

bool find(int *matrix, int rows, int cols, int number){
    
    if(matrix != NULL && rows >0 && cols > 0){
	// search from lower left to the upper right  
	// start from bottom row 
	int current_row = rows - 1;
	// start from first column 
	int current_col = 0;
	
	while(current_row >=0 && current_col < cols){
	    if( matrix[current_row * cols + current_col] == number ){
		cout<<"The number "<<number<<" is found ";
		cout<<"at row ("<<current_row+1<<"), column ("<<current_col+1<<")"<<endl;
		return true;
	    }else{
		if(matrix[current_row *  cols + current_col] > number){
		    // go up and search above element in the same column
		    current_row--;
		}else{
		    // go right and search element in the same row
		    current_col++;
		}
	    }
	}
    }else{
	cout<<"invalid matrix (NULL pointer passed) or out of range "<<endl;
	return false;
    }
    cout<<number<<" is not found"<<endl;
    return false;
}

代码:

git clone https://github.com/zhutiti/Hehaitao.git

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter