arrays - 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 实际上是如何按定义进行基数排序的。

如果您已经构建了 Trie，并且所有子集具有相同数量的元素，则 trie 的叶子是按顺序排列的子集，其中叶子的深度是每个子集的元素数。

使用 Trie，你有 O(m) 其中 m = 子集的数量

或者您可以尝试基数排序，其中您有 Ω(n * m) 其中 n = 子集的大小

..希望这可以帮助