搜索二维矩阵 (Java)

x33g5p2x  于2022-09-25 转载在 Java  
字(0.6k)|赞(0)|评价(0)|浏览(166)

编写一个高效的算法,在 m x n 矩阵中搜索一个值。 该矩阵具有以下性质:

  1. 每行中的整数从左到右排序。 2) 每行的第一个整数大于前一行的最后一个整数。

例如,考虑以下矩阵:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

给定目标 = 3,返回 true。

Java 解决方案

这是一个典型的二分查找问题。

您可以尝试通过先查找行然后查找列来解决此问题。 没有必要这样做。 由于矩阵的特殊性,矩阵可以被认为是一个排序数组。 目标是使用二分搜索在这个排序数组中找到元素。

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null || matrix.length==0 || matrix[0].length==0) 
            return false;
 
        int m = matrix.length;
        int n = matrix[0].length;
 
        int start = 0;
        int end = m*n-1;
 
        while(start<=end){
            int mid=(start+end)/2;
            int midX=mid/n;
            int midY=mid%n;
 
            if(matrix[midX][midY]==target) 
                return true;
 
            if(matrix[midX][midY]<target){
                start=mid+1;
            }else{
                end=mid-1;
            }
        }
 
        return false;
    }
}

相关文章

微信公众号

最新文章

更多