矩阵元素查找

[编程题]矩阵元素查找

热度指数：28444 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

已知一个有序矩阵mat，同时给定矩阵的大小n和m以及需要查找的元素x，且矩阵的行和列都是从小到大有序的。设计查找算法返回所查找元素的二元数组，代表该元素的行号和列号(均从零开始)。保证元素互异。

数据范围： $0 \le n,m \le 1000$ ，矩阵中的任何元素满足 $0 < mat_{i,j} \le 1000000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n+m)$

示例1

输入

[[1,2,3],[4,5,6]],2,3,6

输出

[1,2]

示例2

输入

[[1,2,3]],1,3,2

输出

[0,1]

算法知识视频讲解

Python

随机也是一种规律

# 直接暴力咯

class Solution:

def findElement(self, mat, n, m, x):
# write code here
for i in range(n):
for j in range(m):
if mat[i][j] == x:
return [i, j]
return 0

发表于 2020-12-05 20:37:37 回复(0)

Python

Yannyezixin

# -*- coding:utf-8 -*-

class Solution:
    def findElement(self, mat, n, m, x):
        if n < 1 and m < 1:
            return []
        
        i = 0
        j = m - 1
        
        while i < n and j >= 0:
            if mat[i][j] == x:
                return [i, j]
            elif mat[i][j] < x:
                i += 1
            else:
                j -=1
        return []

发表于 2016-08-08 14:55:26 回复(0)