示例:
现有矩阵 matrix 如下:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5,返回 true。
给定 target = 20,返回 false。
限制:
0 <= n <= 1000
0 <= m <= 1000
注意:本题与主站 240 题相同:https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
由于题目说明了横和竖都是非递减,可以想到利用二分查找来判断。
最基础的思路是对数组的每一个子数组进行二分查找,可以利用竖行也是非递减来稍稍进行剪枝。
时间复杂度是O(n * log(m))
更好的方法是把数组稍稍旋转一下,可以发现,变成了一颗左节点小于等于父节点,右节点大于等于父节点的二叉树。
这样可以将时间复杂度降到O(m + n)
二分查找:
class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { int len1 = matrix.length - 1; if (len1 == -1) { return false; } int len2 = matrix[0].length - 1; if (len2 == -1) { return false; } int up = 0; int down = len1; // 进行剪枝 while (matrix[up][len2] < target) { if (++ up > down) { return false; } } // 进行剪枝 while (matrix[down][0] > target) { if (-- down < up) { return false; } } for (; up <= down; up ++) { if (search(matrix[up], 0, len2, target)) { return true; } } return false; } // 对每一个子数组都进行二分查找。 private boolean search(int[] arr, int left, int right, int target) { while (left < right) { int mid = (left + right) / 2; if (arr[mid] < target) { left = mid + 1; } else if (arr[mid] > target) { right = mid - 1; } else { return true; } } return arr[left] == target; } }
二叉树:
class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { if (matrix.length == 0 || matrix[0].length == 0) { return false; } int i = 0; int j = matrix[0].length - 1; while (j >= 0 && i < matrix.length) { if (matrix[i][j] > target) { j --; } else if (matrix[i][j] < target) { i ++; } else { return true; } } return false; } }