gpt4 book ai didi

LeetCode:搜索二维矩阵题解

转载 作者:知者 更新时间:2024-03-13 09:06:01 30 4
gpt4 key购买 nike

题干

请写出一个高效的在m*n矩阵中判断目标值是否存在的算法,矩阵具有如下特征:
每一行的数字都从左到右排序
每一行的第一个数字都比上一行最后一个数字大

用例

例如对于下面矩阵:

[
    [1,   3,  5,  9],
    [10, 11, 12, 30],
    [230, 300, 350, 500]
]

要搜索的目标值为3,返回true;
示例1
输入:

[[1,3,5,9],[10,11,12,30],[230, 300, 350, 500]],3

返回值:

true

解答

有效信息:

  • 每一行的数字都从左到右递增
  • 每一行的第一个数字都比上一行最后一个数字大

故此此矩阵有序,可用二分查找取值。

方法一:两次二分查找

可以先通过二分查找确定 行,再对该 行 继续进行二分查找 ,常规思维:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowIndex = binarySearchFirstColumn(matrix, target);
        if (rowIndex < 0) {
            return false;
        }
        return binarySearchRow(matrix[rowIndex], target);
    }

    public int binarySearchFirstColumn(int[][] matrix, int target) {
        int low = -1, high = matrix.length - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (matrix[mid][0] <= target) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    public boolean binarySearchRow(int[] row, int target) {
        int low = 0, high = row.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
}
复杂度分析

时间复杂度:
O ( log ⁡ m + log ⁡ n ) = O ( log ⁡ m n ) O ( l o g m + l o g n ) = O ( l o g m n ) O(\log m+\log n)=O(\log mn)O(logm+logn)=O(logmn)O(logm+logn)=O(logmn)O(logm+logn)=O(logmn)
其中 mm 和 nn 分别是矩阵的行数和列数。

空间复杂度:O ( 1 ) O(1)O(1)。

方法二:一次二分查找

因为每一行的第一个数字都比上一行最后一个数字大 ,所以我们可通过 数学的方法 将其压缩为一个 一维矩阵

import java.util.*;
public class Solution {
    /**
     *
     * @param matrix int整型二维数组
     * @param target int整型
     * @return bool布尔型
     */
    public boolean searchMatrix (int[][] matrix, int target) {
        // write code here
        int M = matrix.length, N = matrix[0].length,left = 0, right = M * N - 1;
        while (left <= right) {
            int center = ( right - left) / 2 + left;
            int compute = matrix[center / N][center % N];
            if (compute < target) {
                left = center + 1;
            } else if (compute > target) {
                right = center - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}
复杂度分析

时间复杂度:O(logmn),其中 m是矩阵的行 和 n 是矩阵的列
空间复杂度:O(1),原有数组上进行操作,未申请额外空间

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com