大厂面试真题题解:搜索二维矩阵

写出一个高效的算法来搜索 m × n矩阵中的值。
这个矩阵具有以下特性:

  • 每行中的整数从左到右是排序的。
  • 每行的第一个数大于上一行的最后一个整数。

在线评测地址:领扣题库官网

样例 1:

        输入: [[5]],2
        输出: false
        
        样例解释: 
  没有包含,返回false。

样例 2:

        输入:  
[
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
],3
        输出: true
        
        样例解释: 
        包含则返回true。

解题思路:
题目提到,给定的数组已经排序,若是一个一维数组,直接一次二分查找即可。现在题目给了一个二维数组,那么处理一下数组的下标,仍然按照一维数组二分即可。
二分查找常用于查找有序数组中目标数target的位置,用left和right记录target所在的区间端点,每次将区间的中间位置值和target作比较,然后移动区间端点。
算法流程:

  • 将数组matrixi下标转换为 i*col + j, 问题即转换为一维数组二分查找问题
  • 将区间赋值为整个数组区间(left = 0, right = n*m - 1),取中间位置mid
  • 若a[mid] < target,则将区间缩小到原区间的右区间(left = mid + 1)
  • 若a[mid] > target,则将区间缩小至原区间的左区间(right = mid)
  • 若a[mid] = target,返回true
  • 当left >= right 时,若a[right] = target则返回true, 否则返回false
    复杂度分析:
  • 时间复杂度:O(log(nm))
  • 即将二维数组看作一个n*m大小的一维数组,二分查找值。
  • 空间复杂度:O(1)
  • 查找不需要开辟新的空间,只需在原数组基础上进行查找即可
    代码:
public class Solution {
    /**
     * @param matrix, a list of lists of integers
     * @param target, an integer
     * @return a boolean, indicate whether matrix contains target
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length;
        int col = matrix[0].length;
        int left = 0, right = n*col - 1;
        
        while(left < right){
            int mid = (right + left) / 2;
            if(matrix[mid/col][mid%col] == target){
                return true;
            }
            else if(matrix[mid/col][mid%col] > target){
                right = mid;
            }
            else{
                left = mid + 1;
            }
        }
        
        if(matrix[right/col][right%col] == target){
            return true;
        }
        
        return false;
    }
}

更多题解参考:九章官网Solution

上一篇:【小米OJ-找到第N个数字Ⅱ】


下一篇:[CS:APP]程序间的交互和通信