链接
https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
难度： #中等
题目
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 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/
代码框架
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
}
}
题目解析
每一行都按照从左到右递增的顺序排序，
每一列都按照从上到下递增的顺序排序,
可以分析得到，
每一行的最左边是最小值，最右边是最大值，
每一列的最上边是最小值，最下边是最大值，
进一步分析，
左上角的元素是最小值，
右下角的元素是最大值，
左下角的元素是第一列和最后一行的中间值，
右上角的元素是第一行和最后一列的中间值。
解答思路1：
先循环二维数组的每一行，
对每一行的有序数据进行二分查找，
找到则返回true，
找不到就二分查找下一行，
如果全部都找不到，
返回false。
解答思路2：
利用二维数组自身提供的有序性，
进行二分思想的查找，
最左下角的元素是第一列和最后一行的中间值，
左下角的元素比当前列上面的值都大，
也比当前行后面的值都小，
使用i,j记录所在的元素，
最先开始比较最左下角的元素，
如果该元素比target大，则i--上移，
如果该元素比target小，则j++右移，
直到找到target，返回true。
画图演示思路：
测试用例
package edu.yuwen.sowrd.num04.solution;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import edu.yuwen.sowrd.num04.sol2.Solution;
public class SolutionTest {
/**
* 现有矩阵 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。
*/
@Test
public void testCase1() {
Solution solution = new Solution();
int[][] 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 } };
int target = 5;
boolean isFind = solution.findNumberIn2DArray(matrix, target);
Assertions.assertTrue(isFind);
}
/**
* 现有矩阵 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 = 20，返回 false。
*/
@Test
public void testCase2() {
Solution solution = new Solution();
int[][] 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 } };
int target = 20;
boolean isFind = solution.findNumberIn2DArray(matrix, target);
Assertions.assertFalse(isFind);
}
/**
* 现有矩阵 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 = 1，返回 true。
*/
@Test
public void testCase3() {
Solution solution = new Solution();
int[][] 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 } };
int target = 1;
boolean isFind = solution.findNumberIn2DArray(matrix, target);
Assertions.assertTrue(isFind);
}
/**
* 现有矩阵 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 = 30，返回 true。
*/
@Test
public void testCase4() {
Solution solution = new Solution();
int[][] 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 } };
int target = 30;
boolean isFind = solution.findNumberIn2DArray(matrix, target);
Assertions.assertTrue(isFind);
}
/**
* 现有矩阵 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 = 15，返回 true。
*/
@Test
public void testCase5() {
Solution solution = new Solution();
int[][] 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 } };
int target = 15;
boolean isFind = solution.findNumberIn2DArray(matrix, target);
Assertions.assertTrue(isFind);
}
/**
* 现有矩阵 matrix 如下：[
* [1,2,3,4,5],
* [6,7,8,9,10],
* [11,12,13,14,15],
* [16,17,18,19,20],
* [21,22,23,24,25]]
* 给定 target = 19，返回 true。
*/
@Test
public void testCase6() {
Solution solution = new Solution();
int[][] matrix = { { 1, 2, 3, 4, 5 }, { 6, 7, 8, 9, 10 },
{ 11, 12, 13, 14, 15 }, { 16, 17, 18, 19, 20 },
{ 21, 22, 23, 24, 25 } };
int target = 19;
boolean isFind = solution.findNumberIn2DArray(matrix, target);
Assertions.assertTrue(isFind);
}
/**
* 现有矩阵 matrix 如下：[
* [2,5],
* [2,8],
* [7,9],
* [7,11],
* [9,11]]
* 给定 target = 7，返回 true。
*/
@Test
public void testCase7() {
Solution solution = new Solution();
int[][] matrix = { { 2, 5 }, { 2, 8 }, { 7, 9 }, { 7, 11 }, { 9, 11 } };
int target = 7;
boolean isFind = solution.findNumberIn2DArray(matrix, target);
Assertions.assertTrue(isFind);
}
}
解答1
package edu.yuwen.sowrd.num04.sol1;
public class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
for (int i = 0; i < matrix.length; i++) {
// 对每一行的有序数据进行二分查找
boolean isFind = binarySearch(matrix[i], target);
// 找到即可立即返回
if (isFind) {
return true;
}
}
// 全部都找不到
return false;
}
/**
* 二分查找数组中目标
*/
private boolean binarySearch(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (target == nums[mid]) {
return true;
}
if (target < nums[mid]) {
high = mid - 1;
}
if (target > nums[mid]) {
low = mid + 1;
}
}
return false;
}
}
解答2 推荐
package edu.yuwen.sowrd.num04.sol2;
public class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
// 计算矩阵的行数和列数
int n = matrix.length;
int m = matrix[0].length;
// 最左下角，开始比较的元素位置
int i = n - 1;
int j = 0;
while (i >= 0 && j < m) {
int cur = matrix[i][j];
if (cur == target) {
return true;
}
// 元素上移，朝着较小的数据移动
if (cur > target) {
i--;
}
// 元素右移，朝着较大的数据移动
if (cur < target) {
j++;
}
}
return false;
}
}
网友评论