限制条件：
- O(1) 空间
- 准时
这不是一个家庭作业问题，只是我遇到的一个有趣的问题。
以下是我能想到的一些解决方案，但在给定的限制下没有任何解决方案。
Method 1
*具有 O(n) 内存 *
- 递归地将数组分为两部分。 （继续划分直到每个子问题的大小
- 对每个子问题进行排序，首先使用数组，最后使用数字。
- 合并子问题数组
Method 2
在 O(n log n) 时间内
- 根据字典顺序对数组进行排序，它变为 1234abcd
- 反转数组 4321dcba 的两半
- 反转整个字符串 abcd1234
Method 3
如果定义了数字范围
另外，如果数字在特定范围内，那么我可以初始化一个 int 说 track= 0;
当我遇到数组中的数字时设置适当的位
例如 (1
Method 4如果我们想消除整数范围的限制，我们可以将方法 3 与 HashMap 一起使用，但这样会需要更多内存。
无法想出更好的方法来解决 O(1) 时间和 O(n) 空间中的通用问题。
这里的一般问题是指：
给定序列 x1y1x2y2x3y3....xnyn
其中 x1 , x2 是字母 x1
有什么建议 ？
What is n？假如说n是输入的大小：
这称为列表的卷积。本质上，你必须转换一个对的列表(a,1),(b,2),(c,3),(d,4)到一对列表(a,b,c,d),(1,2,3,4)。它与矩阵转置的操作相同。
无论如何，您必须将结构视为 k 维数组，其中 k = lg n。数组的卷积是当您将索引 i 处的值按位旋转“移动”到索引 i 时得到的结果。在本例中，我们希望将索引向右旋转 1 位。这意味着卷积是最大循环长度为k的排列。诀窍是从每个循环中选择一个索引 - 这将始终包括 0 和 n-1。
编辑：实际上，您可能想要的是将排列分解为转置的乘积。然后，您需要做的就是交换。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
