时间戳

首页 > 解决方案 > 一个测试用例显示超出时间限制。为什么？

python - 一个测试用例显示超出时间限制。为什么？

问题描述

问题 - 给定一个 0 和 1 的 mxn 矩阵，如果一个元素为 0，则将其整行和整列设置为 0。就地执行。

def value(arr):
    lk=[]
    ll=[]
    for i in range(m):
        for j in range(n):
            if(arr[i][j]==0):
                lk.append(i)
                ll.append(j)

    for ele in lk:
        for j in range(n):
              arr[ele][j]=0
    for ele in ll:
        for i in range(m):
            arr[i][ele]=0

    for i in range(m):
        for j in range(n):
            print(arr[i][j],end=' ')
        print()


str=input().split()
m,n=int(str[0]),int(str[1])
arr = [[0 for j in range(n)] for i in range(m)]

value(arr)

标签： python

解决方案

这个问题没有很好地解释，因为你没有告诉测试用例是什么。但这没关系，因为您是 StackOverflow 的新手。

经过一番谷歌搜索，我发现这是 leetcode 中的一个问题。首先，代码可以工作，但速度很慢。在像 leetcode 这样的竞争性编程中，您应该编写一个非常优化的代码，可以在最短的时间内解决问题。

    def setZeroes(matrix):

        R = len(matrix)
        C = len(matrix[0])
        rows, cols = set(), set()

        # Essentially, we mark the rows and columns that are to be made zero
        for i in range(R):
            for j in range(C):
                if matrix[i][j] == 0:
                    rows.add(i)
                    cols.add(j)

        # Iterate over the array once again and using the rows and cols sets, update the elements
        for i in range(R):
            for j in range(C):
                if i in rows or j in cols:
                    matrix[i][j] = 0

如您所见，您和建议的答案都有嵌套循环。但是建议的答案只有两个循环，而您的答案有 4 个循环。

我希望您能理解为什么您的代码有效但效率低下。

推荐阅读