这里是完整问题的链接:https://youtu.be/5dJSZLmDsxk 问题:创建一个函数,返回二维数组中负整数的个数,使得数组中每一行的整数从索引 0 到 n 增加大小,而每一列的整数从上到下增加大小. 例如
{{-5, -4, -3, -2},
{-4, -3, -2, -1},
{-3, -2, -1, 0},
{-2, -1, 0, 1}}
在视频中,CS Dojo 提出了以下解决方案:
def func(M, n, m):
count = 0
i = 0
j = m - 1
while j >= 0 and i < n:
if M[i][j] < 0:
count += j + 1
i += 1
else:
j -= 1
return count
我的问题是:为什么/下面的代码效率不高? (唯一的区别是后者从左边开始,并且它递增 count
多次 <-- 但是这两件事会有什么不同吗?
int rows = 3;
int cols = 4;
int count_neg(const int arrays[rows][cols]) {
int count = 0;
int pos = cols;
for (int i = 0; i < rows; i++) {
for (int j = 0; j <= pos; j++) {
if (arrays[i][j] < 0)
count++;
else {
pos = j;
break;
}
}
if (pos == 0)
break; /*offers miniscule efficiency improvement?*/
}
return count;
}
请假设它们都是用同一种语言编写的。
最佳答案
不同之处在于第二个版本扫描所有负数矩阵,并花费 O(n*m) 时间(整个矩阵可能是负数),而第一个版本追踪之间的边界负元素和非负元素,并花费 O(n+m) 时间。
要了解第一个如何工作,请考虑:每次迭代都会增加 i
或减少 j
。 i
只能递增n-1 次,j
只能递减m-1 次。
关于python - 两种算法的效率比较 : Find the number of negative integers in a row-wise/column-wise sorted matrix,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55778255/