【Leetcode 74】搜索二维矩阵 —— 二分查找|矩阵

简介: 给你一个满足下述两条属性的`m x n`整数矩阵:每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数

74. 搜索二维矩阵

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

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。
    给你一个整数target,如果target在矩阵中,返回true;否则,返回false

示例 1:

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

题目分析

矩阵

算法思路:

  1. 依次将每行最后一个数与 target 对比,若matrix[row][n] < target则对比下一行末的元素
  2. 遍历 target 所在行,进行数字匹配
class Solution {
   
   
    public boolean searchMatrix(int[][] matrix, int target) {
   
   
        int row = 0, n = matrix[0].length - 1, m = matrix.length;
        while(row < m && matrix[row][n] < target){
   
   
            row++;
        }
        if(row >= m){
   
   
            return false;
        }
        // 遍历
        for(int num : matrix[row]){
   
   
            if(num == target){
   
   
                return true;
            }
        }
        return false;
    }
}

二分查找

算法思路:

  1. 把矩阵视为元素个数为m * n - 1的升序一维数组进行二分查找

二分查找算法是用分治策略实现对n个元素进行排序的算法。详细可见 分治法的基本思想与例子解析

class Solution {
   
   
    public boolean searchMatrix(int[][] matrix, int target) {
   
   
        int m = matrix.length, n = matrix[0].length;
        int low = 0, high = m * n - 1;
        while (low <= high) {
   
   
            int mid = (high - low) / 2 + low;
            int x = matrix[mid / n][mid % n];
            if (x < target) {
   
   
                low = mid + 1;
            } else if (x > target) {
   
   
                high = mid - 1;
            } else {
   
   
                return true;
            }
        }
        return false;
    }
}
相关文章
|
1月前
|
算法
力扣240 搜索二维矩阵II
力扣240 搜索二维矩阵II
|
3月前
leetcode:374. 猜数字大小(二分查找)
leetcode:374. 猜数字大小(二分查找)
15 0
|
3月前
|
算法 测试技术 C#
【二分查找】LeetCode1970:你能穿过矩阵的最后一天
【二分查找】LeetCode1970:你能穿过矩阵的最后一天
|
1月前
|
机器学习/深度学习 人工智能 算法
LeetCode刷题--- 面试题 01.07. 旋转矩阵(原地旋转+翻转替旋转)
LeetCode刷题--- 面试题 01.07. 旋转矩阵(原地旋转+翻转替旋转)
|
3月前
|
算法 测试技术 C#
map|二分查找|离线查询|LeetCode:2736最大和查询
map|二分查找|离线查询|LeetCode:2736最大和查询
|
3月前
|
算法 测试技术 C#
【map】【动态规划】LeetCode2713:矩阵中严格递增的单元格数
【map】【动态规划】LeetCode2713:矩阵中严格递增的单元格数
|
3月前
|
算法 测试技术 C#
【二分查找】【双指针】LeetCode:2565最少得分子序列
【二分查找】【双指针】LeetCode:2565最少得分子序列
|
3月前
|
缓存 算法 测试技术
【单调栈】【二分查找】LeetCode: 2454.下一个更大元素 IV
【单调栈】【二分查找】LeetCode: 2454.下一个更大元素 IV
|
3月前
|
算法 机器人 测试技术
二分查找|双指针:LeetCode:2398.预算内的最多机器人数目
二分查找|双指针:LeetCode:2398.预算内的最多机器人数目
|
3月前
|
算法 测试技术 C#
【二分查找】LeetCode:2354.优质数对的数目
【二分查找】LeetCode:2354.优质数对的数目