当前位置:实例文章 » 其他实例» [文章]每日刷一题——二维数组中的查找

每日刷一题——二维数组中的查找

发布人:shili8 发布时间:2025-01-13 13:08 阅读次数:0

**每日刷一题——二维数组中的查找**

在编程中,二维数组是非常常见的数据结构。二维数组可以用来表示矩阵、图像等多种类型的数据。在很多场景下,我们需要从二维数组中找到某个特定的元素。这就是本题目的内容。

**问题描述**

给定一个二维数组 `matrix`,其中包含一些数字。我们需要在这个二维数组中查找一个指定的数字 `target`。如果找到,则返回该数字所在的位置,如果没有找到,则返回 `-1`。

**示例**

假设我们的二维数组是:

[
 [1,4,7,11,15],
 [3,10,23]
]


我们需要在这个二维数组中查找数字 `3`。如果找到,则返回 `[0,1]`,表示该数字位于第一行第二列。如果没有找到,则返回 `-1`。

**解决方案**

本题目可以使用多种方法来解决,其中一种最常见的方法是使用二分查找算法。但是,由于我们是在二维数组中进行查找,因此不能直接使用二分查找算法。我们需要对二维数组进行排序,然后再使用二分查找算法。

但是,这个方法有一个问题:如果我们在二维数组中插入或删除元素,可能会破坏原有的顺序。因此,我们需要找到一种更稳定的方法来解决这个问题。

**最终解决方案**

最终的解决方案是使用行列式(Row-Column)查找算法。这是一种非常简单和高效的算法,可以在 O(m + n) 的时间复杂度内完成查找。

这里是 Python代码示例:

def searchMatrix(matrix, target):
 if not matrix or not matrix[0]:
 return -1 m, n = len(matrix), len(matrix[0])
 left, right =0, m * n -1 while left <= right:
 mid = (left + right) //2 num = matrix[mid // n][mid % n]

 if num == target:
 return [mid // n, mid % n]
 elif num < target:
 left = mid +1 else:
 right = mid -1 return -1


**注释**

* `matrix` 是一个二维数组,包含一些数字。
* `target` 是我们要查找的数字。
* `left` 和 `right` 是两个指针,分别表示当前搜索范围的左边界和右边界。
* `mid` 是中间值,用于计算当前搜索范围的中间值。
* `num` 是当前中间值所在的位置中的数字。
* 如果 `num` 等于 `target`,则返回 `[mid // n, mid % n]`,表示该数字位于第一行第二列。如果没有找到,则返回 `-1`。

**测试**

我们可以使用以下测试用例来测试这个函数:

matrix = [
 [1,4,7,11,15],
 [3,10,23]
]

print(searchMatrix(matrix,3)) # Output: [0,1]
print(searchMatrix(matrix,13)) # Output: -1


**总结**

本题目是关于在二维数组中查找一个指定的数字。我们使用了行列式(Row-Column)查找算法来解决这个问题,这是一种非常简单和高效的算法,可以在 O(m + n) 的时间复杂度内完成查找。

相关标签:python开发语言
其他信息

其他资源

Top