当前位置：首页 > news >正文

240.搜索二维矩阵

news 来源：原创 2024/6/30 23:53:32

·题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

输入：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

示例 2：

输入：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

·解题思路

想编写一个二维二分查找的算法，就是说将二维矩阵分为四个象限，根据中间值的大小判断要搜索的区域。但是每次对比完还需要查找余下三个象限的值，时间耗费比较多。

----如果想做该算法，需要搞清楚的事情是。当中间值小于 target时候，需要查找的三个象限为左上、左下、右上；当中间值大于 target 的时候，需要查找的三个象限为右上、左下、右下。

·Java代码


class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;for(int i = 0; i < m ; i ++){int[] temp = matrix[i];if(find(temp, target, 0, n - 1)){return true;}}return false;}public static boolean find(int[] arr, int target, int lo, int hi ) {if(lo > hi ) return false;int mid = lo + (hi - lo ) / 2;if(arr[mid] == target){return true;}else if(arr[mid] > target){return find(arr, target, lo, mid - 1);}else{return find(arr, target, mid + 1, hi);}}
}

------耗时太长了，还不如每一行使用二分查找。但是做一点点小小的优化，只有当每一行的第一个元素小于 target ，并且最后一个元素大于 target 的时候，才进行二分查找。

·Java 代码

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;for(int i = 0; i < m ; i ++){int[] temp = matrix[i];if(temp[0] <= target && temp[n - 1] >= target){if(find(temp, target, 0, n - 1)){return true;}}}return false;}public static boolean find(int[] arr, int target, int lo, int hi ) {if(lo > hi ) return false;int mid = lo + (hi - lo ) / 2;if(arr[mid] == target){return true;}else if(arr[mid] > target){return find(arr, target, lo, mid - 1);}else{return find(arr, target, mid + 1, hi);}}
}

当然还有一个暴力遍历求解就不说了。