167 - 74 搜索二维矩阵 - 001

题目

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。

示例 1:

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

示例 2:

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

解答

这个数组的条件如此严苛，令我有点想把它拍扁成一位数组，然后二分查找。。

或者直接调原生api，一个个数组找😂

这题不配中等难度哈哈哈

原生api

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for item in matrix:
            if target in item:
                return True
        return False

Runtime: 68 ms, faster than 85.18% of Python3 online submissions for Search a 2D Matrix.

Memory Usage: 14.9 MB, less than 5.88% of Python3 online submissions for Search a 2D Matrix.

var searchMatrix = function(matrix, target) {
  for (const item of matrix) {
    if (item.includes(target)) {
      return true
    }
  }
  return false
};

Runtime: 56 ms, faster than 66.91% of JavaScript online submissions for Search a 2D Matrix.

Memory Usage: 34.3 MB, less than 100.00% of JavaScript online submissions for Search a 2D Matrix.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        arr = []
        for item in matrix:
            arr += item
        if target in arr:
            return True
        else:
            return False

Runtime: 64 ms, faster than 93.52% of Python3 online submissions for Search a 2D Matrix.

Memory Usage: 14.8 MB, less than 5.88% of Python3 online submissions for Search a 2D Matrix.

var searchMatrix = function(matrix, target) {
  let arr = []
  for (const item of matrix) {
    arr = arr.concat(item)
  }
  if (arr.includes(target)) {
    return true
  } else {
    return false
  }
};

Runtime: 60 ms, faster than 41.85% of JavaScript online submissions for Search a 2D Matrix.

Memory Usage: 36.6 MB, less than 50.00% of JavaScript online submissions for Search a 2D Matrix.

双指针

https://leetcode-cn.com/problems/search-a-2d-matrix/solution/sou-suo-er-wei-ju-zhen-by-leetcode/

就是把二维数组当成一位数组，用公式算出对应一位数组的位置。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        if n == 0:
            return False

        left = 0
        right = m*n-1
        while left < right:
            mid = (left+right) >> 1
            ele = matrix[mid//n][mid % n]
            if ele < target:
                left = mid+1
            else:
                right = mid
        if matrix[left//n][left % n] == target:
            return True
        else:
            return False

Runtime: 64 ms, faster than 93.52% of Python3 online submissions for Search a 2D Matrix.

Memory Usage: 14.8 MB, less than 5.88% of Python3 online submissions for Search a 2D Matrix.

var searchMatrix = function(matrix, target) {
  const m = matrix.length
  if (m === 0) {
    return false
  }
  const n = matrix[0].length
  if (n === 0) {
    return false
  }
  let left = 0,
    right = m * n - 1
  while (left < right) {
    let mid = (left + right) >> 1
    let ele = matrix[~~(mid / n)][mid % n]
    if (ele < target) {
      left = mid + 1
    } else {
      right = mid
    }
  }
  if (matrix[~~(left / n)][left % n] == target) {
    return true
  } else {
    return false
  }
};

Runtime: 56 ms, faster than 66.91% of JavaScript online submissions for Search a 2D Matrix.

Memory Usage: 34.3 MB, less than 100.00% of JavaScript online submissions for Search a 2D Matrix.