检查矩阵的行是否在 O(1) 时间内充满 1

Question

我有一个作业，需要用 C 语言编写一个函数，该函数检查给定矩阵中是否有一行充满“1”。矩阵值只能是“1”或“0”( bool 矩阵)。

例如:(尺寸 3)

1 1 0  
1 1 1  
0 0 1  

returns 1 (true)

1 1 0  
1 0 1  
1 0 0  

returns 0 (false)

现在，它非常简单，没有任何限制，但后来我被要求以 O(1) 的时间复杂度执行此操作，我不知道从哪里开始。

如果有帮助:我们被要求在此之前编写 2 个函数:

1. init(n, A) 在 O(n^2) 中用“1”填充 n 大小的矩阵 A
2. flip(A, i ,j) 将 [i,j] 处的值从 '0' 变为 '1' 或 '1' 变为 '0'，时间复杂度为 O(1)

Answer 1

问题是之前已经完成了“会计工作”，现在只需在恒定时间内获取结果即可。

这里可以应用不同的策略。在 O(n^2) 时间内用 1 秒初始化矩阵后，现在每次翻转，您都可以跟踪:

• 1
• 翻转(或等效的 0)

如果您选择跟踪 1，则每个矩阵需要额外的 O(n) 内存来存储它们。当您翻转 1 时，您会从 ones-on-a-row 数组中减去 1。当您翻转 0 时，就会向您的 Ones-on-a-row* 数组添加 1。

如果您跟踪翻转，则按行进行，并且您再次需要 O(n) 额外内存。同样，您有一个辅助数组，其中存储每行的翻转次数。如果翻转后新值是 0 - 加一，如果翻转后新值是 1 - 减一。

然后，在您的 O(1) 函数中，您只需检查相应数组位置处的行存储值即可。