力扣74——搜索二维矩阵
原题
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true
示例 2:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false
原题url：https://leetcode-cn.com/problems/search-a-2d-matrix/
解题
二分查找
既然是已经排好序的，那么我第一想到的就是二分查找了。每次进行对半查找，时间复杂度O(log(mn))，应该还是很高效。
我准备将查找分成两部分，第一是二分查找找到 target 在哪一行，然后从那一行再利用二分查找找到 target 在这一行的哪个位置。
让我们来看看代码：
class Solution {
// 总行数
int row;
// 总列数
int col;
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0) {
return false;
}
row = matrix.length;
col = matrix[0].length;
// 利用二分法查询
return binarySearchMatrix(matrix, 0, matrix.length - 1, target);
}
/**
* 查找这是矩阵的哪一行
*/
public boolean binarySearchMatrix(int[][] matrix, int left, int right, int target) {
if (left > right) {
return false;
}
if (left == right) {
int[] array = matrix[left];
if (target < array[0] || target > array[col - 1]) {
return false;
}
// 从数据中心查找
return binarySearchArray(array, 0, col - 1, target);
}
int middle = (left + right) / 2;
int[] middleArray = matrix[middle];
if (middleArray[0] > target) {
return binarySearchMatrix(matrix, left, middle - 1, target);
} else if (middleArray[col - 1] < target) {
return binarySearchMatrix(matrix, middle + 1, right, target);
} else {
return binarySearchArray(middleArray, 0, col - 1, target);
}
}
/**
* 查找这是数组中的哪个位置
*/
public boolean binarySearchArray(int[] array, int left, int right, int target) {
if (left > right) {
return false;
}
if (left == right) {
return array[left] == target;
}
int middle = (left + right) / 2;
if (array[middle] > target) {
return binarySearchArray(array, left, middle - 1, target);
} else if (array[middle] == target) {
return true;
} else {
return binarySearchArray(array, middle + 1, right, target);
}
}
}
提交OK，其执行用时：1 ms，内存消耗：38.3 MB。
优化
虽然解题成功，且效果不错，但总感觉这样写的太过。因为我将二维数组的查找分为两种情况，如果以后变成三维、四维数组，岂不是代码更长？其实这种查找都是利用的同一种思想——二分查找，那我们是否可以将其进行合并呢？
可以的，我们可以将二维数组拉长。拉成1层后，就可以直接用一维数组中的二分查找了。
让我们看看代码：
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int col = matrix[0].length;
// 将二维数组拉成一维数组，利用二分法解决
int left = 0;
int right = matrix.length * col - 1;
while (left <= right) {
// 计算中间数的下标和值
int middleIndex = (left + right) / 2;
int middleVal = matrix[middleIndex / col][middleIndex % col];
if (middleVal == target) {
return true;
}
if (middleVal < target) {
left = middleIndex + 1;
} else {
right = middleIndex - 1;
}
}
return false;
}
}
提交OK，其执行用时：0 ms，内存消耗：40.9 MB。
大家知道这多余的内存消耗在哪儿呢？按道理说，跟前面的方法相比，这里不涉及递归，理论上其调用栈更少，内存消耗应该更少才对。如果大家知道的话，可以在下方评论，我将感激不尽。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题应该主要就是涉及到二分查找，然后加一些优化，应该就没有问题了。
有兴趣的话可以访问我的博客或者关注我的公众号，说不定会有意外的惊喜。
https://death00.github.io/
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-12-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录