LeetCode第74题搜索二维矩阵

继续打卡算法题，今天学习的是LeetCode第74题搜索二维矩阵，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些提升。

分析一波题目

看完题目，暴力解决很容易想到，完整遍历一次二维矩阵就知道结果了。但是暴力解法需要的时间复杂度是O(n), 有没有时间复杂度更低的解法呢？

我们根据题目说明，可以把二维矩阵转化为一个升序的一维数组，这样就可以使用二分搜索法了，有序是能够使用二分搜索法的关键。

因此本题，我们的难题在于把二分搜索过程中产生的中间数，转换成二维数组的横坐标和纵坐标。

start = 0

end = m*n -1

计算中位数：mid = (end-start)/2 + start

计算所在行（横坐标）：mid / m

计算所在列（竖坐标）：mid % m

本题解题技巧

1、将有序的二维数组转化有序的一维数组

2、将一维数组的元素位置转换成二维数组的横坐标和竖坐标

编码解决

class Solution {
   
   
    public boolean searchMatrix(int[][] matrix, int target) {
   
   
        int m = matrix.length, n = matrix[0].length;
        int start = 0, end = m * n - 1;
        while (start <= end) {
   
   
            int mid = (end - start) / 2 + start;
            //转换成成二维数组的横坐标，竖坐标
            int x = matrix[mid / n][mid % n];
            if (x < target) {
   
   
                low = mid + 1;
            } else if (x > target) {
   
   
                end = mid - 1;
            } else {
   
   
                return true;
            }
        }
        return false;
    }
}

总结

1、本题巧妙的点在于将二维降为一维问题，难点在于将一维的位置转换成二维矩阵的坐标。