[Leetcode] Search a 2D Matrix 搜索二维矩阵

elisa.yang 发布于2019-08-14 12:34 / 2635人阅读

摘要：由于数组的特性，我们可以从二维数组的右上角出发，如果目标小于该数，则向左移动左边的数字肯定更小，而当前列中所有数字都比该数字大。

Search a 2D Matrix I

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. For example,
Consider the following matrix:
[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

二分法 复杂度

时间 O(log(MN)) 空间 O(1)

思路

我们可以把二维数组想象成一个一维数组，第一行尾连着第二行头，第二行尾连着第三行头...同样是有个最小值最大值，二分得到中间值，通过对中间值取模可以得到对应二维数组的下标。这样，该题就转化为了一维有序数组二分搜索的题了。

注意

二分搜索的几个边界条件是min<=max，min=mid+1,max=mid-1

代码

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if(m == 0) return false;
        int n = matrix[0].length;
        int min = 0, max = m * n - 1;
        while(min <= max){
            int mid = min + (max - min) / 2;
            int row = mid / n;
            int col = mid % n;
            if(matrix[row][col] == target){
                return true;
            } else if (matrix[row][col] < target){
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        return false;
    }
}

2018/2

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not matrix[0]:
            return False
        rows = len(matrix)
        cols = len(matrix[0])
        min, max = 0, rows * cols - 1
        while min <= max:
            mid = min + (max - min) // 2
            row = mid // cols
            col = mid % cols
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] < target:
                min = mid + 1
            elif matrix[row][col] > target:
                max = mid - 1
        return False

Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom. For example,
Consider the following matrix:
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.

贪心法 复杂度

时间 O(N+M) 空间 O(1)

思路

虽说该方法叫贪心法不太得当，但是贪心最能描述该方法的过程。由于数组的特性，我们可以从二维数组的右上角出发，如果目标小于该数，则向左移动（左边的数字肯定更小，而当前列中所有数字都比该数字大）。如果该数比目标小，则向下移动（下边的数字肯定更大，而当前行的所有数字逗比该数字小）。这样反复重复该过程就能找到目标数。如果直到左下角都没有该数，说明找不到该数。同样的，这题也可以从左下角向右上角寻找。

代码

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0){
            return false;
        }
        int i = 0, j = matrix[0].length - 1;
        while(i < matrix.length && j >= 0){
            int curr = matrix[i][j];
            if(curr == target){
                return true;
            // 比目标小则向下
            } else if(curr > target){
                j--;
            // 比目标大则向左
            } else {
                i++;
            }
        }
        return false;
    }
}

2018/2

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not matrix[0]:
            return False
        rows = len(matrix)
        cols = len(matrix[0])
        row, col = 0, cols - 1
        while row >= 0 and row < rows and col >=0 and col < cols:
            if matrix[row][col] > target:
                col -= 1
            elif matrix[row][col] < target:
                row += 1
            elif matrix[row][col] == target:
                return True
        return False

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64563.html

leetcode 240. Search a 2D Matrix II

摘要：代码如下超时当然了，这个方法不出意外，超时了思路二二分法查找我们采用二分法的思想，将矩阵分解为更小的矩阵从而每一次筛选确保能够去除掉一个子矩阵范围。从而我们可以将目标值锁定在左上方的子矩阵上。题目要求 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has t...

lanffy 2019-08-16 11:03 评论0 收藏0
leetcode74. Search a 2D Matrix

摘要：题目要求假设存在这样一个二维数组，该数组从左到右，从上到下均递增，且下一行第一个值比上一行最后一个值大。总计的时间复杂度为，代码如下二维二分法如何能之间在二维数组上使用二分法呢。题目要求 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the foll...

niuxiaowei111 2019-08-15 10:41 评论0 收藏0
leetcode 48 Rotate Image

摘要：题目详情这道题目要求我们对一个正方形矩阵进行顺时针度的翻转。并且要求不声明额外的空间，不能新建二维数组。输入数组旋转后的输入数组想法这道题因为要求在位。所以我们需要找到一种解法，使得每次操作都是交换两个元素的位置，最后实现整个矩阵的旋转。题目详情 You are given an n x n 2D matrix representing an image.Rotate the ima...

kgbook 2019-08-15 14:17 评论0 收藏0
leetcode363. Max Sum of Rectangle No Larger Than K

摘要：思路一暴力循环如果我们将矩阵中的每个子矩阵都枚举出来，并计算其元素和，从而得出小于的最大值即可。题目要求 Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k. E...

nemo 2019-08-16 17:57 评论0 收藏0
[Leetcode] Word Search I&II 二维字符矩阵查找单词

摘要：复杂度时间空间为长度，为大小空间复杂度是是因为我用存信息，只动态地存当前的路径如果用来存信息的话空间复杂度就是时间复杂度对每个点都要作为起始点，对于每个起始点，拓展一次有四个可能性四个邻居，要拓展次长度为。思路暴力搜索带走。 Word Search I Given a 2D board and a word, find if the word exists in the grid. ...

LuDongWei 2019-08-14 14:06 评论0 收藏0