给定n个单词，是否可以按字典顺序对它们进行排序，其中o（n）时间复杂度？我发现了一种方法，比如创建一个trie数据结构，并且trie的顺序遍历会导致时间复杂度接近于O（kn），其中k是任意字符串长度，但这里的问题是空间复杂性 . 构建BST和顺序遍历也是一个不错的选择，但时间复杂度是O（nlogn） . 因此，任何人都可以建议我，考虑到两者的限制，那将是更好的BST或trie . 还欢迎任何其他算法或建议 .
使用bucket sort或radix sort对 O(nL) 时间内的单词进行排序很容易 . 这里 L 是字长 . 要做得更好是不可能的，因为你必须至少看一次所有键 .
O(nL)
L
你的triesort想法很旧 .
1 回答
使用bucket sort或radix sort对
O(nL)时间内的单词进行排序很容易 . 这里L是字长 . 要做得更好是不可能的，因为你必须至少看一次所有键 .你的triesort想法很旧 .