O（n）中的2键搜索算法

Question

我必须找到一种算法来对O（n）复杂度中的数组进行排序。 数组长度为n，有两个不同的键。

例如这个数组中的java：

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

结果应该是

1 1 
1 2 
2 1 

我解决这个问题挣扎..

谁也许能帮助我吗？

在此先感谢

Answer 1

如果您的数据存储在Trie，然后DFT（深度优先遍历）会告诉你你的特里是如何被定义实际上是基数排序。

如果您已经构建了Trie，并且所有子集都具有相同数量的元素，则树的树叶依次为子集，树叶的深度为每个子集的元素数。

使用特里，你有O（m），其中M =子集

或者你可以尝试一个基数排序，那就是你有Ω（N * M），其中n =一分大小号-set

..hope这有助于