是否有更高效的算法来压扁数组？

我知道递归的方式来压扁嵌套数组。在stackoverflow上有几种解决方案（都在java和javascript - 一些使用内置库）。是否有更高效的算法来压扁数组？

但这些解决方案的时间复杂度是O（n^2）！我想知道是否有一个算法可以做得更好。

在此先感谢您的帮助！

它们看起来像O（n），其中n是元素的数量。我不明白你会如何比这更好。 –

是你所指的数组n的维数，但是如果n是它考虑的元素的数量O（n） – mc20

你链接的JavaScript问题中的“Adam”的答案是线性的，而不是二次的。 @VinceEmigh当在线性时间内做它微不足道是不合理的:) – Pointy

您要么是弄错了，要么将您的n定义为要处理的元素数的根平方。

数组展平问题的所有解决方案都是O（n），其中n取决于元素的总数（因为实际上，您需要扫描它们全部，每个元素只有一次）。展平数组不是一个算法问题，而只是将它放在一个“优雅”片段中的问题。

2017-02-11 17:21:11 fdreger

我明白了。如果我错了，请纠正我，但可以肯定地说它是伪多项式吗？ –

@KarthikVasishta big-O总是多项式的最高阶。 –

谢谢@PeterLawrey –

回答