给定一个数组[a1b2c3d4]转换为[ABCD1234] [英] Given an array [a1b2c3d4] convert to [abcd1234]
问题描述
约束：
- O（1）空间
- O（n）的时间
这不仅是一个有趣的问题，我遇到了一个家庭作业的问题。
It is not a homework question just a interesting question I came across.
下面是一些解决方案，我能想到的，但没有什么做它在给定的约束条件。
Here are some solutions I could think of but nothing that does it in given constraints.
方法1
*带O（n）的内存*
*With O(n) memory *
- 分割两部分阵列递归。 （不断分裂，直至大小＆LT; = 2对每个子问题）
- 排序每个子问题阵列的第一和数字的结束。
- 合并子问题阵列
方法2
在为O（n log n）的时间的
- 排序基于阵列的字典顺序就变成1234ABCD
- 在反向阵列4321dcba 的两半
- 反转整个字符串ABCD1234
方法3
如果定义的序列号范围的
此外，如果情况是，数字是在特定的范围，则我可初始化INT说轨道= 0; 并设置相应的位，当我遇到一个数字数组 如（1＆其中;＆其中;一个[2]）。 1.调换字母来排列的前半 在赛道变2.标记号 3.在以后使用的轨道，填补阵列的下半年。
Also if the case was that numbers are in a specific range then I can initialize a int say track= 0; And set the appropriate bit when I come across a number in array eg (1 << a[2] ) . 1. Swap alphabets to first half of array 2. Mark numbers in track variable 3. later use track to fill in second half of array.
方法4 我们可以使用方法3与HashMap的，如果我们要删除的整数范围的约束，但那么它会需要更多的内存。
Method 4 We can use Method 3 with HashMap if we want to remove the constraint of range of integers but then it will need more memory.
想不出更好的办法来解决澳普遍的问题（1）时间及O（n）的空间。
Cannot think of a better way to solve the generic problem in O(1) time and O(n) space.
在这里普遍的问题是指：
Generic Problem here refers to:
给定顺序x1y1x2y2x3y3 .... xnyn 但是x1，x2是字母X1＆其中; X2＆LT; ...＆LT; XN 和Y1Y2 ...炔都是整数。 Y1＆LT; Y2＆LT; ...＆LT; YN 安排为X1X2 ... xny1y2 ... YN
Given a sequence x1y1x2y2x3y3....xnyn where x1 , x2 are alphabets x1 < x2 <.... < xn and y1y2...yn are integers . y1 < y2 <.... < yn Arrange the output as x1x2...xny1y2...yn
有什么建议？
推荐答案
什么是 N ？假设 N 是输入的大小：
What is n? Assuming that n is the size of the input:
此被称为列表的卷积。从本质上讲，你要对（一，1），（B，2），（C，3），（D，4）的列表转换为一对名单（A，B，C，D），（1,2,3,4）。这是相同的操作，以矩阵的转置。
This is called the convolution of a list. In essence, you have to convert a list of pairs (a,1),(b,2),(c,3),(d,4) to a pair of lists (a,b,c,d),(1,2,3,4). It's the same operation as the transpose of a matrix.
不管怎样，你必须要考虑结构的一个k维数组，其中K = LGñ。数组的卷积就是你，当你动值的指数我的索引我按位旋转。在这种情况下，我们要旋转的指标向右1比特。这意味着，卷积是与k的最大周期长度的置换。特技然后从每个周期中选择一个索引 - 这将总是包括0和n-1
Anyway, you have to think of the structure as a k-dimensional array, where k = lg n. The convolution of the array is what you get when you "move" the value at an index i to index i bitwise rotated. In this case, we want to rotate the indices rightward 1 bit. This means that the convolution is a permutation with a maximum cycle length of k. The trick is then selecting one index from each cycle – this will always include 0 and n-1.
编辑：其实，你可能想要的是分解置换成换位的产物。然后，所有你需要做的是交换。
Actually, what you probably want is to decompose the permutation into a product of transpositions. Then, all you need to do is swaps.
这篇关于给定一个数组[a1b2c3d4]转换为[ABCD1234]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
