如何降低时间复杂度？
如何降低时间复杂度？
提问于 2020-04-30 17:40:32
下面的问题是:从N×m的矩阵中选择一个元素，我们必须从每一行中选择一个元素来构成大小为N的新数组A。我们希望找到数组A中任意两个相邻元素之间绝对差的最小可能值(注意:从第1行中选择的元素将成为A1，从第2行中选择的元素将成为A2，等等)。
示例ip(用于2X2矩阵) :
8 4
6 8样本op :
0 #(8-8)我已经尝试过以下代码，但是在时间限制为1秒的情况下，它花费了大量的时间(5秒)。有人能帮助提高代码的复杂性吗..。
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
minimum=abs(l[0][0]-l[1][0])
for i in range(n):
if i+1<n:
for j in range(m):
for k in range(m):
diff=abs(l[i][j]-l[i+1][k])
if diff==0:
minimum=diff
break
elif diff<minimum:
minimum=diff
else:
continue
print(minimum)回答 1
Stack Overflow用户
回答已采纳
发布于 2020-05-01 19:28:53
a idea
让我们考虑以下矩阵：
8 4 3
6 8 1取第1行和第2行，并生成一个向量。因为我们还想知道哪个元素属于哪一行，所以请将这些元素打包成它们的行号。
two_rows = [(8,1), (4,1), (3,1) (6,2), (8,2), (1,2)]这意味着我们有8，4，3从第1行，和6，8，1从第2行。
sorted_two_rows = [(1,2), (3,1), (4,1), (6,2), (8,1), (8,2)]接下来，遍历这个列表。只考虑来自不同行的相邻元组。
(1,2)和(3,1)(4,1)，(6,2)(6,2)，(8,1)(8,1)和(8,2)
其余的简单明了，只需计算绝对差并记录最小值。
如果对所有相邻行重复此操作。你应该找出总体上最小的差别。这将需要O(nm log m)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/61529519
复制相关文章
相似问题
腾讯云开发者
