arrays - O（n）の2キー検索アルゴリズム

Question

O（n）の複雑さで配列をソートするアルゴリズムを見つける必要があります。配列の長さはnで、2つの異なるキーがあります。

たとえば、Javaのこの配列：

int[][] array = {{1,2},{2,1},{1,1}};

結果は次のようになります

1 1
1 2
2 1

私はこの問題を解決するのに苦労しています。

誰が私を助けることができるでしょうか？

前もって感謝します

Answer 1

データがTrieに保存されている場合、DFT（Depth First Traversal）は、Trieが実際にどのように基数でソートされているかを示します。

Trieを作成し、すべてのサブセットに同じ数の要素がある場合、Trieの葉は順番にサブセットになり、葉の深さはサブセットごとの要素数になります。

Trieを使用すると、O（m）が得られます。ここで、m=サブセットの数です。

または、基数ソートを試すことができます。ここで、Ω（n * m）があります。ここで、n=サブセットのサイズです。

..お役に立てれば