【剑指offer】从二维递增数组中进行查找

亦凉 2024-05-25 17:32 25阅读 0赞

## ✨前言✨： ##

**算法是一个程序员的内功，能很好的体现程序员的编程思维，通过学习和掌握常见的算法，不仅能提高coding能力，还能更加容易在笔面试中脱颖而出。本专栏将记录博主刷算法题的过程，不定期的会更新一些优质的算法题。如果对大家有帮助，别忘了三连支持哟！**

--------------------

**目录**

✨前言✨：

?题目?

✨思路分析✨：

具体思路详解：

图解数组自我更新过程：

✨代码展示：✨

--------------------

## **?题目?** ##

> **?：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个 函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。时间复杂度 O(row+col)。**

> **?：数组样例** 
> 
> **int arr\[4\]\[4\] = \{** 
> 
> **1,2,8,9,** 
> 
> **2,4,9,12,**
> 
> **4,7,10,13,**
> 
> **6,8,11,15 \};**

--------------------

## ✨思路分析✨： ##

### 具体思路详解： ###

**?这题我们经过思考后，会发现有两个难点：**

**1：如何写出满足时间复杂度的算法？**

**2：如何通过递增关系进行行列排除？**

**因为要满足时间复杂度，所以通过循环嵌套对二维数组遍历显然不行。在这时我们看题目发现递增的条件还没有用，所以我们考虑通过递增关系来进行行列排除，这样我们就不必遍历二维数组的每一个元素，每次排除一行或一列效率自然高很多，但如何进行行列排除呢？**

**此时我们就需要选择一个关键点，即排除的起始点，若要写出满足时间复杂度的算法，我们只能选择左下脚或者右上脚作为关键点。现在我以左下角作为关键点，来示范具体该如何去操作。**

> **?1：将关键点的原始值与k进行比较。**
> 
> **2：若关键点的值大于k，又因为每一行都是递增序列，则这一行的所有数均大于k，此时我们将这一行排除掉，然后关键点向上移动，找小的数。若关键点的值小于k，则这一列的所有数均小于k，此时我们将这一行排除掉，然后关键点向右移动，找大的数。**
> 
> **3：将排除掉一行或一列的数组视为自我更新后的数组，然后在继续比较新关键点的值与k的大小关系，重复这三步。**
> 
> **4：如果找到了k就退出这个循环，如果关键点从左下角移动至右上角均没有找到k则返回找不到。**

### 图解数组自我更新过程： ###

> **?现在我们进行图解：**
> 
> **![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_76_color_FFFFFF_t_70_g_se_x_16][]**

### ✨**代码展示：**✨ ###

**由上述分析可知，每一次进行行列排除和数组自我更新的方式均是一样的，所以显然可以进行递归，现在我展示非递归和递归两个版本，建议大家先自己敲一篇，再食用下文效果最佳。**

**?非递归：**

#include<stdio.h>
    int Find_k(int arr[4][4], int k, int row, int col)
    {
    	int r = row - 1;//找到关键点
    	int c = 0;
    	while (r >= 0 && c < col)//确保每次自我更新时数组中还有元素
    	{
    		if (arr[r][c] == k)
    		{
    			return 1;//返回1表示找到了
    		}
    		if ( arr[r][c] > k)
    		{
    			r--;
    			continue;
    		}
    		if (  arr[r][c] < k)
    		{
    			c++;
    			continue;
    		}
    
    	}
    	return 0;//若遍历完整个数组都没有找到，则返回0
    }
    int main()
    {
    	int arr[4][4] = {
    1,2,8,9,
    2,4,9,12,
    4,7,10,13,
    6,8,11,15
    	};
    	int k = 0;
    	int ret = 0;
    	int col = sizeof(arr[0]) / sizeof(arr[0][0]);
    	int row = sizeof(arr) / sizeof(arr[0][0]) / col;
    	ret = Find_k(arr, k, row,col );
    	if (ret == 1)
    	{
    		printf("找到了");
    	}
    	else
    	{
    		printf("没有找到");
    	}
    
    	return 0;
    }

**?递归版本：**

#include<stdio.h>
    int flag = 0;
    //返回1表示找到了
    //返回0表示没有找到
    int Find_k(int col, int k, int row, int(*arr)[4])
    {
    	int r = row - 1;
    	int c = 0;
    	if (arr[r][c] == k||r<0||c>=col)//判断是找到了，或是越界
    	{
    		if (arr[r][c] == k)
    		{
    			flag = 1;
    			return 1;
    		}
    		else
    		{
    			return 0;
    		}	
    	}
    	if (arr[r][c] > k)
    	{
    		Find_k(col,k,row-1,arr);
    	}
    	if (arr[r][c] < k)
    	{
    		Find_k(col + 1, k, row, arr);
    	}
    	if (flag == 1)
    	{
    		return 1;
    	}
    	else
    	{
    		return 0;
    	}
    }
    int main()
    {
    	int arr[4][4] = {
    1,2,8,9,
    2,4,9,12,
    4,7,10,13,
    6,8,11,15
    	};
    	int k = 0;
    	int ret = 0;
    	int col = sizeof(arr[0]) / sizeof(arr[0][0]);
    	int row = sizeof(arr) /sizeof(arr[0][0])/col;
    	ret=Find_k(col,k,row,arr);
    	if (ret == 1)
    	{
    		printf("找到了");
    	}
    	else
    	{
    		printf("没有找到");
    	}
    
    	return 0;
    }

**以上代码，还可做优化在此仅作参考，若有更好的算法，还望能够私信告知，多谢各位。**

--------------------

**由于本人水平十分有限，若有错误请即使告知！如果有帮助别忘了，万分感谢。**

**点赞? 收藏✨ 关注✌**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_76_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/25/9698d94b5af74c0897e7a149dfa846c4.png