算法题--在行列都有序的二维矩阵中查找指定元素

image.png

0. 链接

题目链接

1. 题目

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.
Example 1:

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

Example 2:

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

2. 思路1：二维矩阵当成一维数组+二分查找

• 按照从左到右、从上到下的顺序，将二维矩阵看成一个包含m*n个元素的一维数组，然后运用二分查找即可

3. 代码

# coding:utf8
from typing import List


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

        col = len(matrix[0])

        left = 0
        right = row * col - 1
        while left <= right:
            mid = (left + right) >> 1
            i = mid // col
            j = mid % col
            if matrix[i][j] < target:
                left = mid + 1
            elif matrix[i][j] > target:
                right = mid - 1
            else:
                return True

        return False


def print_matrix(matrix):
    for each in matrix:
        print(each)
    print('=' * 50)


def my_test(solution, matrix, target):
    print('input:')
    print_matrix(matrix)
    print('output:{}'.format(solution.searchMatrix(matrix, target)))


solution = Solution()
my_test(solution, [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
], 3)
my_test(solution, [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
], 13)
my_test(solution, [], 0)

输出结果

input:
[1, 3, 5, 7]
[10, 11, 16, 20]
[23, 30, 34, 50]
==================================================
output:True
input:
[1, 3, 5, 7]
[10, 11, 16, 20]
[23, 30, 34, 50]
==================================================
output:False
input:
==================================================
output:False

4. 结果

image.png