LeetCode刷题之搜索二维矩阵

2024 7/5 一如既往的晴天，分享几张拍的照片嘿嘿，好几天没做题了，在徘徊、踌躇、踱步。蝉鸣的有些聒噪了，栀子花花苞也都掉落啦，今天给他剪了枝，接回一楼来了。ok，做题啦！

图1、宿舍阳台摄，每天都是如此美景

图2、吃饭路上桥上摄

图3、桥的另一边摄
okok，做题啦！

1、题目描述

2、算法分析

要求设计一个高效的算法在矩阵中搜索我们想要的元素。我所能想到的就只有暴力解法：

 public boolean searchMatrix(int[][] matrix, int target) {
        for(int[] row : matrix ){
            for(int x : row){
                if(x == target){
                    return true;
                }
            }
        }
        return false;   
    }

暴力解法感觉很爽啊，思路简单。为什么简单的解法往往性能不简单呢？收益高的往往需要更多的付出呢？空间复杂度和时间复杂度往往不能正相关呢？一切似乎都与能量守恒有关。一切似乎都被设定，而我就是一个没有台词的NPC。哈哈，太tm矫情了，矫揉造作，继续想想有没有什么好的方法。
是有的，由于矩阵每一行都是升序排列的，所以我们遍历每一行后，再进行二分查找，看目标值是否在矩阵中。

3、代码

public boolean searchMatrix(int[][] matrix, int target) {
        // 遍历矩阵的每一行  
        for(int[] row : matrix){
            // 对当前行执行二分查找，寻找目标值
            int index = binarySearch(row, target);
            // 如果在当前行找到了目标值（即index >= 0），则返回true
            if(index >= 0){
                return true;
            }
        } 
        // 如果遍历完所有行都没有找到目标值，则返回false
        return false;
    }
    // 定义一个辅助方法，用于对一维数组进行二分查找  
    // 参数：nums是要搜索的一维数组，target是要搜索的目标值  
    // 返回值：如果找到目标值，则返回目标值在数组中的索引；如果没有找到，则返回-1
    public int binarySearch(int[] nums, int target){
        // 初始化查找范围的上下界
        int low = 0, high = nums.length - 1;
        // 当查找范围不为空时，进行查找
        while(low <= high){
            // 计算中间索引，防止溢出 
            int mid = (high - low) / 2 + low;
            // 获取中间元素的值
            int temp = nums[mid];
            // 如果中间元素等于目标值，则返回其索引
            if(temp == target){
                return mid;
            // 如果中间元素大于目标值，则在左半部分继续查找 
            }else if(temp > target){
                high = mid - 1;
            // 如果中间元素小于目标值，则在右半部分继续查找
            }else{
                low = mid + 1;
            } 
        }
        // 如果遍历完整个数组都没有找到目标值，则返回-1
        return -1;
    }

4、复杂度分析

• 时间复杂度：O(mlogn)。对一行使用二分查找的时间复杂度为 O(logn)，最多需要进行 m 次二分查找。
• 空间复杂度：O(1)。

5、Z形查找

okok，还有更妙的一个算法呢，本来打算不写了，发现这个算法妙得很啊，Z字形查找。
Z形查找：

1. 选择起始搜索点：由于矩阵的每一行和每一列都是有序的，从矩阵的右上角（或左下角，取决于搜索策略）开始搜索是一个很好的选择。这里选择右上角是因为它允许我们同时利用行和列的排序特性。
2. 比较与移动：在搜索过程中，我们不断地将当前元素与目标值进行比较。如果当前元素等于目标值，则搜索成功，返回true。如果当前元素大于目标值，由于列是升序的，我们可以确定目标值不可能在当前列的更上方（即更靠近矩阵顶部的位置），因此我们将搜索范围缩小到当前列的左方一列。相反，如果当前元素小于目标值，由于行是升序的，我们可以确定目标值不可能在当前行的更左方（即更靠近矩阵左侧的位置），因此我们将搜索范围缩小到当前行的下一行。
3. 迭代搜索：重复上述比较与移动的过程，直到找到目标值或搜索范围为空（即已经遍历到矩阵的左下角或右上角之外的位置）。

public boolean searchMatrix(int[][] matrix, int target) {
         // 获取矩阵的行数和列数
        int m = matrix.length, n = matrix[0].length;
        // 初始化搜索的起始位置，从矩阵的右上角开始  
        // 选择右上角是因为这样可以同时利用行和列的排序特性来缩小搜索范围
        int x = 0, y = n - 1;
        // 当没有越界时，继续搜索
        while(x < m && y >= 0){
            // 如果当前元素等于目标值，则搜索成功，返回true 
            if(matrix[x][y] == target){
                return true;
            }
            // 如果当前元素大于目标值，由于列是升序的，所以目标值不可能在当前列的更上方  
            // 因此，将搜索范围缩小到当前列的左方一列 
            if(matrix[x][y] > target){
                y--;
            // 如果当前元素小于目标值，由于行是升序的，所以目标值不可能在当前行的更左方  
            // 因此，将搜索范围缩小到当前行的下一行 
            }else{
                x++;
            }
        }
        // 如果遍历完所有可能的搜索范围都没有找到目标值，则返回false 
        return false;
      }

该算法的思想是通过选择合适的起始搜索点，并利用矩阵的行和列都是有序的这一特性，通过不断缩小搜索范围来高效地找到目标值或确定目标值不存在于矩阵中。

复杂度分析——Z查找

• 时间复杂度：由于每次比较后，搜索范围都会缩小一行或一列，因此该算法的时间复杂度为O(m+n)，其中m是矩阵的行数，n是矩阵的列数。这是因为算法最多会遍历矩阵的每一行和每一列各一次。
• 空间复杂度：该算法的空间复杂度为O(1)，因为它只使用了常数个变量来存储搜索过程中的状态（如当前行索引x、当前列索引y以及矩阵的行数m和列数n），而没有使用额外的数据结构来存储搜索过程中的中间结果。

okok，拜拜啦！做完啦