排序這些n^2數字的最快方法是什麼？

給定一個數字'n'，我想返回包含所有k1 * k2值的n^2數字的排序數組，其中k1和k2的範圍可以從1到n。例如對於n = 2，它將返回：{1,2,2,4}。（該數字基本上是1 * 1,1 * 2,2 * 1,2 * 2）。排序這些n^2數字的最快方法是什麼？

並且對於n = 3它將返回：{1,2,2,3,3,4,6,6,9}。

（數字感：1 * 1,2 * 1,1 * 2,2 * 2,3 * 1,1 * 3,3 * 2,2 * 3,3 * 3）

我嘗試使用從C++標準庫中的排序功能，但我想知道是否可以進一步優化。

來源

2017-03-23 ash

我不是一個職業選手，但也許你可以看看那些可視化：https://www.toptal.com/developers/sorting-algorithms我希望這可以幫助 – Murf

它是一個excersize？編程比賽？ – user31264

@Murf嗨！我們顯然可以使用一些排序算法，但我認爲這裏可能有一些特定情況的解決方案，我無法弄清楚。 – ash

那麼，首先，您會得到n^2條目，其中最大的條目是n^2，並且可能的取值範圍只有很小的值用於較大的n。所以，我建議計數方法：

初始化大小n^2與零數組counts[]。
遍歷你的數組值values[]，並做counts[values[i]-1]++。
重新初始化values陣列通過該counts陣列迭代的i+1儘可能多的值落入values陣列爲counts[i]給你。

就是這樣。這是O(n^2)，所以你很難找到更高性能的解決方案。

來源

2017-03-23 12:20:49 cmaster

這是O（n^2），如果你使用一致的定義'n' – anatolyg

@anatolyg是的，你是對的，固定的。 – cmaster

這對於「大n？」來說不是很昂貴嗎？我想這取決於你的意思是「大」。當n是100萬時，你說的是分配一個萬億項目的數組。我想說這個算法對於「小到中等」是可行的。 –

vector<int> count(n*n+1); 
for (int i = 1; i <= n; ++i) 
    for (int j = 1; j <= n; ++j) 
     ++count[i*j]; 
for (int i = 1; i <= n*n; ++i) 
    for (int j = 0; j < count[i]; ++j) 
     cout << i << " ";

這實質上就是cmaster的答案中所描述的O（n * n）解決方案。

來源

2017-03-23 12:20:38 Henrik

雖然此代碼片段可能會解決問題，[包括解釋]（http：//meta.stackexchange。com/questions/114762/explain-completely-code-based-answers）確實有助於提高帖子的質量。請記住，您將來會爲讀者回答問題，而這些人可能不知道您的代碼建議的原因。 – NathanOliver

排序這些n^2數字的最快方法是什麼？

回答

相關問題