输入 -> 字母表 -> 输出(字母表中数字的索引)-> 新字母表(移动到字母表开头的数字):
3 -> [1, 2, 3, 4, 5] -> 3 -> [3, 1, 2, 4, 5]
2 -> [3, 1, 2, 4, 5] -> 3 -> [2, 3, 1, 4, 5]
1 -> [2, 3, 1, 4, 5] -> 3 -> [1, 2, 3, 4, 5]
1 -> [1, 2, 3, 4, 5] -> 1 -> [1, 2, 3, 4, 5]
4 -> [1, 2, 3, 4, 5] -> 4 -> [4, 1, 2, 3, 5]
5 -> [4, 1, 2, 3, 5] -> 5 -> [5, 4, 1, 2, 3]
输入:(n - 字母中的数字数,m - 要加密的文本长度,文本)
5、6
3 2 1 1 4 5
答案:3 2 1 1 4 5 -> 3 3 3 1 4 5
是否有任何数据结构或算法可以有效地做到这一点,比 O(n*m) 快?
我将不胜感激任何想法。谢谢。
使用订单统计树来存储对(1,1)...(n,n)
,按它们的第一个元素排序。
c
通过选择c
树的第 -th 个最小元素并取其第二个元素来查找字符的翻译。
然后通过删除您查找的节点并将其插入回树中来更新树,该对的第一个元素设置为-t
,其中t
是消息中的位置(或其他一些稳步下降的计数器)。
O(ln n)
如果使用自平衡搜索树(例如红黑树)作为订单统计树的底层树结构,则可以在最坏情况下及时完成查找、删除和插入。
鉴于初始树的元素是按顺序插入的,树结构可以构建在 中O(n)
。
所以整个算法将是O(n + m ln n)
时间,最坏的情况。
可以进一步提高这种用于该情况下n
是大于m
,通过存储用于任何连续的范围树中的节点的唯一的一个节点,但计数它用于秩的顺序统计树中的目的,根据节点的数目有将通常是。
然后从只有一个实际存储的节点开始,当重新排列树时,您将表示范围的节点分成三个:一个节点表示找到值之前的范围,一个代表找到值之后的范围,一个代表实际值。然后将这三个节点插入回,在范围节点的情况下,仅当它们不为空并且第一对元素等于第二对元素时,并且在非范围节点的情况下,具有如前所述的负值。如果找到第一个条目为负的节点,则不会在此拆分。
这样做的结果是树将包含最多O(m)
节点,因此该算法的最坏时间复杂度为O(m ln min(n,m))
。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句