就是那个把A_1,B_1,A_2,B_2,...,A_n,B_n用constant memory和linear time重排成A_1,A_2,...,A_n,B_1,B_2,...,B_n的题，似乎还没人给出解答。我来抛砖引玉一下吧。
首先先假设n是2^k的形式，并且把下标从0开始，那么每个下标都是一个k bit的整数。这样做的好处在于一个很关键的observation：我们要实现的置换就是把每一个下标为(r_1,r_2,...r_k)的数，移动到(r_k,r_1,r_2,r_3,...,r_{k-1})，也就是说，shift right by 1。这样子我们就隐式的表达了这个permutation，而且是一个很好的closed form。
先假设我们已经解决了n=2^k的情况，那么对于一般的n怎么办呢？很简单，把n拆分成2的方幂，分别求解，然后merge。不难看出要merge长度为x和y的数组只需要O(x+y)的时间，总共的merge的时间也就是linear的。
那么再回到n=2^k的情况，虽然找出了一个很好的representation，但并没有解决整个问题。从上面的置换，不难看出拆分成轮换之后的结构。现在的难题在于，对于每个轮换我们只想算一次。也就是说，当处理一个新的下标的时候，我们想知道，它是否已经出现在了之前的轮换中了呢？一个简单的办法是求出每个轮换的最小表示，也就是其中最小的那个下标。只有在处理这个最小下标的时候才进行数组的轮换操作。然而，要判断一个下标是否是所在轮换里最小的那个，需要O(k)的操作，也就是说算法的时间是O(nlogn)的。
那么怎样达到O(n)呢？有很多可能性。比如说，能否用constant time判断最小表示（或者用constant time去update）？或者，并不一定以下标从小到大的顺序update，而是找一个更方便处理的顺序。又或者，如果就用naive的方法判断每个下标是否最小表示，找到一个更小的下标就停，那么amortized time是多少呢？有可能会是O(nloglogn)。总之，还有很多可能的方向，我没来得及细想。就先写在这里，做为抛砖引玉吧。
首先先假设n是2^k的形式，并且把下标从0开始，那么每个下标都是一个k bit的整数。这样做的好处在于一个很关键的observation：我们要实现的置换就是把每一个下标为(r_1,r_2,...r_k)的数，移动到(r_k,r_1,r_2,r_3,...,r_{k-1})，也就是说，shift right by 1。这样子我们就隐式的表达了这个permutation，而且是一个很好的closed form。
先假设我们已经解决了n=2^k的情况，那么对于一般的n怎么办呢？很简单，把n拆分成2的方幂，分别求解，然后merge。不难看出要merge长度为x和y的数组只需要O(x+y)的时间，总共的merge的时间也就是linear的。
那么再回到n=2^k的情况，虽然找出了一个很好的representation，但并没有解决整个问题。从上面的置换，不难看出拆分成轮换之后的结构。现在的难题在于，对于每个轮换我们只想算一次。也就是说，当处理一个新的下标的时候，我们想知道，它是否已经出现在了之前的轮换中了呢？一个简单的办法是求出每个轮换的最小表示，也就是其中最小的那个下标。只有在处理这个最小下标的时候才进行数组的轮换操作。然而，要判断一个下标是否是所在轮换里最小的那个，需要O(k)的操作，也就是说算法的时间是O(nlogn)的。
那么怎样达到O(n)呢？有很多可能性。比如说，能否用constant time判断最小表示（或者用constant time去update）？或者，并不一定以下标从小到大的顺序update，而是找一个更方便处理的顺序。又或者，如果就用naive的方法判断每个下标是否最小表示，找到一个更小的下标就停，那么amortized time是多少呢？有可能会是O(nloglogn)。总之，还有很多可能的方向，我没来得及细想。就先写在这里，做为抛砖引玉吧。
选择“Disable on www.wenxuecity.com”
选择“don't run on pages on this domain”
