1

n*n 要素の 2 次元配列があるとします。

  • すべての行がソートされます
  • すべての列がソートされます

例えば：

1 5 7
2 6 8
3 9 10

1 次元の並べ替えられた配列に変換します。よりも優れた解決策はありますかO(nlog(n))。

4

6 に答える 6

2

少なくとも 1 回は検査しなければn^2ならない要素があるため、複雑さを下回ることはできません。n^2

これを行うアルゴリズムは、標準の k-way マージであり、複雑さは ですN log k。ここで、Nはマージされるアイテムの総数、kはシーケンスの数です。

n*n配列には、マージn*nするアイテムとnシーケンス (行) があります。したがって、上記の式に代入すると、次のようになります。

N log k
N = (n*n)
k = n
(n*n) log n

2D 配列をソートされた 1D 配列に変換するのはn^2 log n.

于 2014-07-24T19:21:27.597 に答える
0

関数 f(x,y) = (f(x),f(y)) を使用して、複雑さを軽減し、2 次元配列を平坦化できます。また、1次元配列を並べ替えます。それは関数なので、ハッシュアルゴリズムに似ており、探しているものではないでしょうか?

于 2012-09-18T19:17:20.113 に答える
0

私は時間を持っています: O(n*n log(2n)) スペース O(2n) アルゴリズム。

基本的な考え方は次のようになります

a[0][0] は確かに最小の要素です。要素は行単位および列単位でソートされるため、次に小さい要素は min( a[0][1], a[1][0] ) になります。たとえば、a[0][1] は 2 つのうち最小であり、次の候補は min(a[0][2],a[1][1],a[1][0]) になります。

等々、

アルゴリズム:

候補要素の最小のものを選び、それを印刷します。潜在的な候補として、要素を最小要素の右と下に押し込みます。（アウトまたはバウンドをチェックします。）候補要素がなくなるまでこれを行います。

DS が必要:

候補要素はヒープを使用して維持できます (上部は最小要素です)。ただし、同じ要素を 2 回プッシュしないようにする必要があります。(y は x の右側、z の下部である可能性があります)。ヒープにプッシュする前に、要素が既にプッシュされているかどうかを知る必要があります。

これらの要件は両方とも、セットによって適切に処理されます (順序付けられます) (i code in c++)

インデックスをセットに格納すると、次の候補要素を候補 D に簡単にプッシュできます。
私の候補dsでは、どの時点でもn + n個以下の要素を維持します。以下は、私が使用する比較関数です。

bool operator()(const int& a,const int& b) const{
        int ai=a/m,aj=a%m;
        int bi=b/m,bj=b%m;
        if(input[ai][aj]!=input[bi][bj])
        return input[ai][aj]<input[bi][bj];
        else
        return a<b;
    }

サンプル実装はこちら: http://ideone.com/w208Af

于 2013-11-27T18:58:06.067 に答える
0

これは O(n) で行うことができます。この場合 n*n=n の場合、時間の複雑さについて話しているときは、リスト内の要素の数を参照しているため、これを n^2 より速く行うことは不可能であることに同意しません。これは、n = min-max の場合の O(n) ソリューションです。これが機能するには、リストに含まれる可能性のある最小数と最大数を知る必要があります。それらが可能な限り最低で最高であることを知る必要はありません。

    int[] Sorted1dArray(int[][] arr, int min, int max)//basically counting sort
    {
       int index = 0;
       int rowColSize = arr[0].Length;
       int[] newArr = new int[max-min];
       int[] ret = new int[rowColSize *rowColSize ];
       for(int i=0;i<rowColSize ;i++)//
       {
          for(int j=0;j<rowColSize ;j++)
             newArr[arr[i][j]]++;
       }
       for(int i=0;i<newArr.Length;i++)
       {
          for(int j=0;j<newArr[i];j++)
          {
             ret[index++]=newArr[j];
          }
       }
       return ret;
    }
于 2014-07-24T17:59:24.053 に答える
0

解決策を投稿する必要がありますO(n log n)。真実は、そのような解決策は実際には不可能です。これが理由です。あなたにはn*n要素があります。したがって、できることはn^2、各要素に少なくとも 1 回アクセスする必要があるためです。考えてみてください。長さの 1 次元配列を埋めるn*n必要があります (つまり、2 次元配列のすべての要素が新しい 1 次元配列に存在する必要があります)。したがって、この問題を で解決する方法はありませんO(n log n)。

于 2012-11-18T22:50:51.977 に答える