在O（n）執行中顯示數字金字塔

Question

我們如何打印以下內容O(n)執行 可能使用單個for循環？

1 
2 3 
4 5 n 

高達n行 我所能做的是使用嵌套的for循環

Answer 1

在C++：

size_t amount = 1; 
size_t count = 0; 
for(size_t i=1;i<=n;++i){ 
    cout << i << " "; 
    ++count; 
    if (count == amount){ 
     cout << endl; 
     count = 0; 
     ++amount; 
    } 
} 

輸出對於n = 29：

1 
2 3 
4 5 6 
7 8 9 10 
11 12 13 14 15 
16 17 18 19 20 21 
22 23 24 25 26 27 28 
29 

的想法跟蹤要在當前行中打印的元素數量，並跟蹤el的數量在當前行中打印的元素。當我們爲當前行打印的元素數量與爲該行打印的元素總數相同時，重置計數並增加下一行要打印的元素數量。你可以混淆格式以獲得更漂亮的輸出，但這是如何在O（n）時間和O（1）空間中完成的要點。

Answer 2

嵌套循環並不一定意味着它不再是O(n)。如果裏面有什麼嵌套循環被執行O(n)次，則嵌套循環是完美的罰款：

cur_num <- 1 
cur_step <- 1 
while cur_num <= n 
    for i <- 1 to cur_step 
     print cur_num++ 
    cur_step++ 
    print '\n' 

有了一個for循環，這是可行的，但是稍微不太愉快

cur_num <- 1 
cur_step <- 1 
cur_step_consumed <- 0 
for i <- 1 to n 
    print cur_num++ 
    cur_step_consumed++ 
    if cur_step_consumed == cur_step 
     cur_step_consumed <- 0 
     cur_step++ 
     print '\n'