2017-03-23 4 views
4

数字「n」が与えられたとき、k1 * k2のすべての値を含むn^2個の数値のソートされた配列を返したいと思います。ここで、k1とk2の範囲は1〜nです。これらのn^2数値をソートする最速の方法は何ですか?

たとえば、n = 2の場合、{1,2,2,4}(数字は基本的に1 * 1,1 * 2,2 * 1,2 * 2)です。

であり、n = 3の場合、{1,2,2,3,3,6,6,9,9}が返されます。

(番号:1で* 1,2 * 1,1 * 2,2 * 2,3 * 1,1 * 3,3 * 2,2 * 3,3 * 3)

I C++標準ライブラリのsort関数を使って試しましたが、さらに最適化できるかどうかは疑問でした。

+0

私はプロソーターではありませんが、おそらくあなたはそれらの視覚化を見ることができます:https://www.toptal.com/developers/sorting-algorithms私はこれが助けてくれることを願っています – Murf

+0

それはexcersizeですか?プログラミングコンテスト? – user31264

+0

@Murfこんにちは!私たちは明らかにいくつかのソートアルゴリズムを使ってそれを行うことができますが、ここでは状況に固有の解決策があると思います。 – ash

答えて

4

まず、n^2のエントリが得られます。そのうちの最大値はn^2であり、可能な値の範囲のうち、小さい値の値が大きいものはnです。だから、私はカウントアプローチをお勧めしたい:

  1. サイズゼロでn^2の配列counts[]を初期化します。
  2. 値の配列values[]を繰り返し、counts[values[i]-1]++を実行します。
  3. countsアレイを反復してvaluesアレイを再初期化し、アレイにi+1という値をいくつかドロップすると、counts[i]が得られます。

それだけです。それはO(n^2)なので、よりパフォーマンスの高いソリューションを見つけることはほとんどありません。

+1

'n'に一貫した定義を使用している場合は、O(n^2)です。 – anatolyg

+0

@anatolygええ、そうです。 – cmaster

+0

これは "大規模なn"のためにこれは法外に高価ではありませんか?私はそれがあなたが "大"の意味に依存していると思います。 nが100万のとき、あなたは1兆個のアイテムの配列を割り当てることを話しています。私はこのアルゴリズムは "中小n"のために実行可能であると言いたい。 –

3
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)解です。

+0

このコードスニペットは、[説明を含む]質問を解決するかもしれませんが(http://meta.stackexchange。com/questions/114762/explain-entire-code-based-answers)は本当にあなたの投稿の質を向上させるのに役立ちます。将来読者の質問に答えていることを覚えておいてください。そうした人々はあなたのコード提案の理由を知らないかもしれません。 – NathanOliver

関連する問題