如果我有一个数组 {1,1,1,1,2,2,3,4,4,4,5,5} 这是一个排序的 5-multiset,大小为 n= 12,k = 5 (不同的键)。什么是基于 O(n log k) 时间比较的算法来为类似的未排序数组排序 k-multiset? 我想到的方法是 3 向分区快速排序。
最佳答案
只需将元素插入平衡二叉搜索树即可产生所需的复杂性。树的每个节点都可以存储到目前为止输入中的值和这些值的计数,就像在计数排序中一样。树的大小最多为 k
,插入次数为 n
,因此总时间为 O(n log k)
。二叉搜索树是基于比较的,因此满足要求。
如果以某种方式完全禁止使用计数,我们可以在树的每个节点中存储相等值的链表,即使只是为了 mock 这种要求。
关于algorithm - 如何获得基于 O(n log k) 时间比较的算法来对 k-multiset 进行排序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49778332/