74.搜索二维矩阵

LeetCode LeetCode 数组 二分查找 矩阵
发布时间 :
字数:1.6k 阅读 : 评论:
  1. 74.搜索二维矩阵
    1. 74.1 题目
    2. 74.2 题解
      1. 暴力法
      2. 二分查找
    3. 74.3 代码
    4. 74.4 运行结果

74.搜索二维矩阵

74.1 题目

给你一个满足下述两条属性的 m x n 整数矩阵：

  1. 每行中的整数从左到右按非严格递增顺序排列。
  2. 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target，如果 target 在矩阵中，返回 true；否则，返回 false。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true`

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出：false`

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -10^4 <= matrix[i][j], target <= 10^4

74.2 题解

暴力法

// 方法一：暴力法
// 该方法通过暴力遍历整个矩阵，逐个比较元素与目标值是否相等来查找目标值。
static bool SearchMatrix1(int[][] matrix, int target)
{
    // 遍历矩阵的每一行
    foreach (var row in matrix)
    {
        // 遍历当前行的每个元素
        foreach (var num in row)
        {
            // 如果当前元素等于目标值，则返回 true，表示找到目标值
            if (num == target)
            {
                return true;
            }
        }
    }

    // 若遍历完整个矩阵仍未找到目标值，则返回 false
    return false;
}

二分查找

// 方法二：二分查找
// 该方法通过将矩阵展开为一个有序的一维数组，然后对这个数组进行二分查找来查找目标值。
static bool SearchMatrix2(int[][] matrix, int target)
{
    // 初始化查找范围的左右边界
    int left = 0;
    // 二维矩阵的长度乘以宽度，再减去 1，得到右边界
    int right = (matrix.Length * matrix[0].Length) - 1;

    // 在左右边界内进行二分查找，直到左边界大于右边界为止
    while (left <= right)
    {
        // 计算中间元素的索引
        int mid = left + (right - left) / 2;
        // 调用辅助函数 GetMatrixVal 获取中间元素的值
        int nowMidVal = GetMatrixVal(matrix, mid);
        // 如果中间元素的值等于目标值，则返回 true，表示找到目标值
        if (nowMidVal == target)
        {
            return true;
        }
        // 如果目标值小于中间元素的值，则目标值可能在左侧，更新右边界为中间元素的左侧
        else if (target < nowMidVal)
        {
            right = mid - 1;
        }
        // 否则，目标值可能在右侧，更新左边界为中间元素的右侧
        else
        {
            left = mid + 1;
        }
    }

    // 若遍历完整个有序数组仍未找到目标值，则返回 false
    return false;
}

// 辅助函数，用于从二维矩阵中获取指定索引位置的元素值
static int GetMatrixVal(int[][] matrix, int index)
{
    // 根据索引计算出元素所在的行数
    int row = index / matrix[0].Length;
    // 根据索引计算出元素所在的列数
    int col = (index % matrix[0].Length);

    // 返回二维矩阵中指定索引位置的元素值
    return matrix[row][col];
}

74.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个满足下述两条属性的 m x n 整数矩阵：
        // 1. 每行中的整数从左到右按非严格递增顺序排列。
        // 2. 每行的第一个整数大于前一行的最后一个整数。
        // 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

        // 示例 1：
        // 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
        // 输出：true

        // 示例 2：
        // 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
        // 输出：false

        // 提示：
        // m == matrix.length
        // n == matrix[i].length
        // 1 <= m, n <= 100
        // -10^4 <= matrix[i][j], target <= 10^4

        #endregion

        #region 测试

        // 示例 1
        int[][] matrix1 = new int[][]
        {
            new int[] { 1, 3, 5, 7 },
            new int[] { 10, 11, 16, 20 },
            new int[] { 23, 30, 34, 60 }
        };
        int target1 = 3;
        bool result1_1 = SearchMatrix1(matrix1, target1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        bool result1_2 = SearchMatrix2(matrix1, target1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[][] matrix2 = new int[][]
        {
            new int[] { 1, 3, 5, 7 },
            new int[] { 10, 11, 16, 20 },
            new int[] { 23, 30, 34, 60 }
        };
        int target2 = 13;
        bool result2_1 = SearchMatrix1(matrix2, target2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        bool result2_2 = SearchMatrix2(matrix2, target2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：暴力法
    // 该方法通过暴力遍历整个矩阵，逐个比较元素与目标值是否相等来查找目标值。
    static bool SearchMatrix1(int[][] matrix, int target)
    {
        // 遍历矩阵的每一行
        foreach (var row in matrix)
        {
            // 遍历当前行的每个元素
            foreach (var num in row)
            {
                // 如果当前元素等于目标值，则返回 true，表示找到目标值
                if (num == target)
                {
                    return true;
                }
            }
        }

        // 若遍历完整个矩阵仍未找到目标值，则返回 false
        return false;
    }

    // 方法二：二分查找
    // 该方法通过将矩阵展开为一个有序的一维数组，然后对这个数组进行二分查找来查找目标值。
    static bool SearchMatrix2(int[][] matrix, int target)
    {
        // 初始化查找范围的左右边界
        int left = 0;
        // 二维矩阵的长度乘以宽度，再减去 1，得到右边界
        int right = (matrix.Length * matrix[0].Length) - 1;

        // 在左右边界内进行二分查找，直到左边界大于右边界为止
        while (left <= right)
        {
            // 计算中间元素的索引
            int mid = left + (right - left) / 2;
            // 调用辅助函数 GetMatrixVal 获取中间元素的值
            int nowMidVal = GetMatrixVal(matrix, mid);
            // 如果中间元素的值等于目标值，则返回 true，表示找到目标值
            if (nowMidVal == target)
            {
                return true;
            }
            // 如果目标值小于中间元素的值，则目标值可能在左侧，更新右边界为中间元素的左侧
            else if (target < nowMidVal)
            {
                right = mid - 1;
            }
            // 否则，目标值可能在右侧，更新左边界为中间元素的右侧
            else
            {
                left = mid + 1;
            }
        }

        // 若遍历完整个有序数组仍未找到目标值，则返回 false
        return false;
    }

    // 辅助函数，用于从二维矩阵中获取指定索引位置的元素值
    static int GetMatrixVal(int[][] matrix, int index)
    {
        // 根据索引计算出元素所在的行数
        int row = index / matrix[0].Length;
        // 根据索引计算出元素所在的列数
        int col = (index % matrix[0].Length);

        // 返回二维矩阵中指定索引位置的元素值
        return matrix[row][col];
    }


    #endregion
}

74.4 运行结果

示例1 方法1 输出：True
示例1 方法2 输出：True
示例2 方法1 输出：False
示例2 方法2 输出：False
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏