矩阵查数

[编程题]矩阵查数

热度指数：5561 时间限制：C/C++ 4秒，其他语言8秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定一个二维整型矩阵，已知矩阵的每一行都按照从小到大的顺序排列，每一列也都按照从小到大的顺序排列。现在给出一个数，请写一个函数返回该数是否存在于矩阵中。

矩阵中出现的数字与需要查找的数(k)都为0~100000之间的整数，且矩阵的大小在3000*3000以内。

在保证正确性的基础上，请尽量给出比较高效的解法。请列出你的算法时间复杂度与空间复杂度分别是多少？

输入描述:

输入两个整数m,n, 且 0<m<=3000, 0<n<=3000。

接着输入一个vector<vector<int>> matrix矩阵，大小为m行n列，与一个int k，为需要查找的数字。

输出描述:

输出true或者false，true表示该数k存在于该matrix矩阵中，false表示该数k不存在于该matrix矩阵中。

示例1

输入

输出

true

说明

4位于矩阵的第二行第二列，故输出true

算法知识视频讲解

Python3

TS9527

之字形走法，复杂度O(m+n)，空间复杂度O(mn)，但是用Python会爆内存

，跟数据结构有关吧。去除两个爆内存的测试用例是可以AC的：

class MainActivity:

    def main(self):
        # Read the data
        m, n = map(int, filter(lambda x: len(x) > 0, input().split(' ')))
        mat = [[0] * n for _ in range(m)]
        for rowPtr in range(m):
            dat = list(filter(lambda x: len(x) > 0, input().split(' ')))
            dat[0] = dat[0].replace('\u200b', '')
            dat = map(int, dat)
            for ptr, num in enumerate(dat):
                mat[rowPtr][ptr] = num
        k = int(input())
        # Initialization
        rowPtr = 0
        colPtr = n - 1
        # Traverse
        while rowPtr < m and colPtr > -1:
            if mat[rowPtr][colPtr] == k:
                print('true')
                return
            if mat[rowPtr][colPtr] > k:
                colPtr -= 1
            else:
                rowPtr += 1
        print('false')


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-08-27 00:10:31 回复(0)