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

3.二维数组中的查找

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

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

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

如:

[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
seo 说:
2021年12月05日 10:45

Their https://www.digitekprinting.com/direct-mail are fast, efficient, and affordable. I can still remember the time when we needed a quick-print for a school project which was a magazine; they were able to help us print it because a lot of printing shops have declined since it is for only one copy, and printing shops usually print in bulk.

anonymous 说:
2023年7月09日 23:09

I would recommend my profile      is important to me, I invite you to discuss this topic. Wildlife Removal Kissimmee

anonymous 说:
2023年7月19日 17:29

I invite you to the page where     see how much we have in common. Orlando Wildlife Removal

anonymous 说:
2023年7月19日 17:32

I should assert barely that its astounding! The blog is informational also always fabricate amazing entitys. Wildlife Removal Oviedo

Cheap Windows VPS Ho 说:
2023年8月27日 22:22

VPS hosting stands for Virtual Private Server hosting, and it refers to a hosting solution where a physical server is divided into multiple virtual servers, each running its own operating system. In this case, the operating system used is Windows. <a href="https://cavpshost.com/ ">VPS hosting windows</a> provides greater control, privacy, and customization options compared to shared hosting, making it ideal for businesses or individuals with specific Windows-based hosting requirements.

VPS Hosting Windows 说:
2023年8月27日 22:23

VPS hosting stands for Virtual Private Server hosting, and it refers to a hosting solution where a physical server is divided into multiple virtual servers, each running its own operating system. In this case, the operating system used is Windows. VPS hosting windows provides greater control, privacy, and customization options compared to shared hosting, making it ideal for businesses or individuals with specific Windows-based hosting requirements.

anonymous 说:
2023年9月12日 04:35

I should assert barely that its astounding! The blog is informational also always fabricate amazing entitys. Hey Dude

anonymous 说:
2023年9月15日 17:15

The blog passage here is undeniably sublime and it should be shared at the site. The all inclusive community who read stuff on that site will genuinely welcome this post and read it and I trust that is useful for everybody.  flower delivery

anonymous 说:
2023年10月01日 18:26

I was failing and referred to this site. Honestly this was one of my greatest life decisions ever. Cannabis


登录 *


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