Leetcode: 【每日一题】- 2019-12-30 - 74. 搜索二维矩阵

[azl397985856]

编写一个高效的算法来判断 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[18sby]

两个月之前做的，思路忘了，占个楼支持一下

var searchMatrix = function(matrix, target) {
  if ( !matrix.length ) return false;
  if ( matrix.length === 1 ) return matrix[0].indexOf( target ) !== -1;
  let row = matrix.length,
      col = matrix[0].length;

  let left = 0,
      right = row - 1;
  while ( left < right ) {
    let mid = Math.floor( (left + right + 1) / 2 );
    if ( matrix[mid][0] <= target && matrix[mid][col - 1] >= target ) {
      left = mid;
      break ;
    }
    else if ( matrix[mid][0] >= target ) {
      right = mid - 1;
    }
    else if ( matrix[mid][col - 1] <= target ) {
      left = mid;
    }
  }
  return matrix[left].indexOf( target ) !== -1;
};

[azl397985856]

和这道题 思路一样，不清楚的可以看一下。

#
# @lc app=leetcode.cn id=74 lang=python3
#
# [74] 搜索二维矩阵
#

# @lc code=start


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

        x = m - 1
        y = 0
        while x >= 0 and y < n:
            if matrix[x][y] > target:
                x -= 1
            elif matrix[x][y] < target:
                y += 1
            else:
                return True
        return False

# @lc code=end

[HEternally]

献丑了；

解法一：二分法

var searchMatrix = function(matrix, target) {
  if (matrix.length === 0 || (matrix.length > 0 && matrix[0].length === 0)) return false;
  let start,mid,num;
  let m = matrix.length,
      n = matrix[0].length,
      end = m * n - 1;
  start = mid = 0;
  while (start <= end) {
      mid = parseInt((start + end) / 2);
      num = matrix[parseInt(mid / n)][mid % n];
      if (target == num) return true;
      else {
          if (target < num) end = mid - 1;
          else start = mid + 1;
      }
  }
  return false;
};

解法二：参考前面思路

var searchMatrix = function(matrix, target) {
        if (matrix.length === 0 || (matrix.length > 0 && matrix[0].length === 0)) return false;
        let m = matrix.length,
            n = matrix[0].length,
            i = 0,
            j = n - 1;
        while(i<m && j>= 0){
            if (matrix[i][j] > target){
                j--;
            }else if (matrix[i][j] < target){
                i++;
            }else {
                return true;
            }
        }
        return false;
}

[unclegem]

Java 题解 简单明了

这题的二维数组明显可以看成是一个一维升序数组，那就好办了，直接二分查找就可以。

    public boolean searchMatrix(int[][] matrix, int target) {

        if (matrix.length == 0)
            return false;

        int rowlen = matrix[0].length;
        int left = 0, right = matrix.length * matrix[0].length - 1;

        while (left <= right) {

            int mid = left + (right - left) / 2;
            int row = mid / rowlen, col = mid % rowlen;
            // one-dim binary search
            if (matrix[row][col] == target)
                return true;
            else if (matrix[row][col] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }

        return false;
    }

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.