这是一个普遍的问题，它可能适用于任何给定的语言，如 C、C++、Java 等。
我想你实现它的任何方式，你都不能比使用 2 个循环更有效，它的效率为 n^2 .
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=1;
我最近在一次采访中被问到这个问题，并且想不出更有效的方法。我从面试官那里得到的只是我可以使用递归或将二维数组转换为链表以使其比 n^2 更有效。任何人都知道这是否可能，如果可以，如何？至少在理论上，如果不是在实践中。
编辑：实际问题给了我两个单元格的坐标，我必须用 1 填充所有可能的最短路径所采用的路径。例如，如果我有一个 5x5 矩阵，我的两个坐标是 (2,0) 和 ( 3,3)，我必须填写：
(2,0)(2,1)(2,2)(2,3) (3,0)(3,1)(3,2)(3, 3）
同时让其余的细胞保持原样。
这取决于你的意思。如果问题是关于普通数组的，这意味着一系列连续的内存位置，并且对于初始化，您的意思是在这个“矩阵”的每个内存位置放置一个值，那么答案是否定的，比 O(n*m) 更好是不可能的并且我们可以证明：
让我们假设算法fill(A[n][m], init_val)是正确的（即填充 的所有内存位置）具有小于（意味着不是 的一部分）的A复杂度，然后足够大，我们将拥有= 内存位置的数量。由于填充内存位置需要一个操作，因此算法可以填充大多数位置[实际上是一半，因为它还必须至少执行一个操作来“选择”不同的内存位置，除非硬件提供组合操作]，这严格小于，这意味着算法不正确。g(n,m)O(n*m)g(n,m)Ω(n*m)nmg(n,m) < n*mfillg(n,m)n*mfill
如果填充内存位置需要恒定时间，这同样适用k，您只需选择更大n的m值。
正如其他已经建议的那样，您可以使用其他数据结构来避免O(n^2)初始化时间。amit 建议使用某种惰性求值，它允许您根本不初始化数组，而仅在访问元素时才这样做。
请注意，这Ω(n^2)在开始时消除了成本，但需要更复杂的操作来访问数组的元素，并且还需要更多的内存。
目前尚不清楚面试官的意思：将数组转换为链表需要Ω(L)时间（其中 L 是数组的长度），因此简单地将整个矩阵转换为链表需要Ω(n^2)时间加上真正的初始化。使用递归根本没有帮助，您最终只会出现重复，例如T(n) = 2T(n/2) + O(1)这将再次导致渐近复杂性没有任何好处。
作为一般规则，所有算法都必须至少扫描所有输入，除非它们事先具有某种形式的知识（例如，元素已排序）。在您的情况下，要扫描的空间是Θ(n^2)，因此每个想要填充它的算法必须至少是Ω(n^2). 任何低于这个复杂度的东西要么做出一些假设（例如内存默认包含初始化值 -> O(1)），要么解决不同的问题（例如使用惰性数组或其他数据结构）。
您可以在 中初始化一个数组O(1)，但它会消耗三倍的空间量，并为矩阵中的每个元素访问额外的“工作”。
因为在实践中，矩阵是内存中的一维数组，所以同样的原理仍然成立。
该页面详细描述了如何完成。