这是完整问题的链接: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 倍。