首页 > 试题广场 >

矩阵查数

[编程题]矩阵查数
  • 热度指数：5522 时间限制：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

输入

3 3
​​2 3 5
​​3 4 7
​​3 5 8
4

输出

true

说明

4位于矩阵的第二行第二列，故输出true
算法知识视频讲解
添加回答
Python
这题太难了头像 这题太难了
这都能过。。。。。 
def main():
    # nlogn
    m, n = list(map(int, input().strip().split()))
    dict = {}
    for i in range(m):
        for j in input().split():
            if j not in dict:
                dict[j] = 1
    k = input()
    print('true') if k in dict else print('false')
if __name__ == '__main__':
    main()

发表于 2020-02-18 17:40:11 回复(0)
Python
zcl_zc头像 zcl_zc
python3 读取数据时为什么会出现数据异常：在读取数据时会报错，用字符串读取显示为：
答案错误:您提交程序的实际输出结果与你的期望输出不一致
代码实际输出：{'2', '\udce2\udc80\udc8b\udce2\udc80\udc8b3', '3', '5', '4', '7', '8'}
你期望的输出：true
思路是：做二维的二分查找
代码如下: 
m,n = mp(int,input().split())
l = []
s = 'false'
for _ in range(m):
    l.append(list(map(int,input().split())))
k = int(input())
bottom,top,left,right = m - 1,0,0,n - 1
while top <= bottom and left <= right:
    mid_s,mid_h = (top + bottom) // 2,(left + right) // 2
    if l[mid_s][mid_h] == k:
        s = 'true'
        break
    elif l[mid_s][mid_h] < k:
        left = mid_h + 1
    elif l[mid_s][mid_h] > k:
        right = mid_h - 1
print(s)


发表于 2019-08-20 17:54:20 回复(0)
Python
薛定谔的胖喵头像 薛定谔的胖喵
m, n = map(int, input().split(' '))
line = [[0] * m] * n
for i in range(m):
    line[i] = list(map(int, input().split(' ')))
k = int(input())

def func():
    global m
    i = 0
    m -= 1
    if m==0 and n==0:
        return 'false'
    while m>=0 and i<n:
        if line[m][i]<k:
            i += 1
        elif line[m][i]>k:
            m -= 1
        else:
            return 'true'
        
    return 'false'

print(func())


内存超了，只有60%，有大佬帮助一下么？
发表于 2019-03-10 10:51:29 回复(0)
Python
990035623头像 990035623 
def FindNumberInSortedArray (arr, num):
    row = len(arr)
    col = len(arr[0])
    i = 0
    j = col-1
    while(i <= row-1 and j >= 0):
        if arr[i][j] == num:
            print('true')
            return
        elif arr[i][j] > num:
            j -= 1
        elif arr[i][j] < num:
            i += 1
    print('false')

if __name__ == '__main__':
    row, col = (int(i) for i in input().split(' '))
    arr = [[int(v)for v in input().split(' ')]for i in range(row)]
    num = int(input())
    FindNumberInSortedArray(arr, num)

这个程序准确率只有60%，提示内存超限，请大佬解释一下。

编辑于 2019-03-05 18:33:56 回复(0)
提交观点

问题信息

数组 算法工程师 第四范式 2019 查找
上传者：小小
难度：
4条回答 6885浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号