是否有更高效的算法來壓扁數組？

我知道遞歸的方式來壓扁嵌套數組。在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 –

回答