对数组排序与线性时间和恒定的空间在替换位置的两个已排序的序列

Antariksha Yelkawar：

这是今天问我在接受采访时，并在问题盯着5分钟之后被踢出。

给定的阵列甲使得所有奇数位置（[的亚序列阿₁，阿₃，阿₅，...]）和所有偶数位置的子序列（[ 阿₂，甲₄，甲₆，...]）是每按排序顺序-例如，[1，7,2，8,3，9,4，10，5]或[3，8,4，11，5]或[5，2,7，4] -排序甲在O（ñ）时间和O（1）空间（包括堆栈空间和输出阵列的空间）。

我已经绞尽脑汁想，拿起我的朋友在这最后两个小时。谷歌没有取得任何答案。我不想颜色的任何意见，但我觉得这可能无法在给定的复杂性来解决。

我们怎样才能解决这个问题？所有输入都理解的。

吉拉德巴坎：

如果（1）的两个交错序列可形成一个单调序列时未交织，并且或者（a）所述阵列具有最低数目的开始和为奇数的长度，或（b）具有最低数目的第二阵列开始序列（一个将是右侧时未交错），并且是偶数长度，我们可以能够扭转算法描述下一个简单的原地算法用于在洗牌（Peiyush耆那，2008年）。

我们将不得不进行“周期前导”序列第一，其次是周期变化。

实施例1

[1, 7, 2, 8, 3, 9, 4, 10, 5]
 1  2  3  4  5  6  7   8  9
 1  6  2  7  3  8  4   9  5

|1| unaffected

   |1     3                |
   m = 4; 2m = 3^2 - 1
   cycles start on 3^0, 3^1
   (4 swaps with 7 and the other
    numbers form a longer cycle.)

实施例2（简单）：

[1, 5, 2, 7, 3]
 1  2  3  4  5
 1  4  2  5  3

|1| unaffected

   |          |
   m = 1
   cycle in 2m => 2, 5
   cycle in 2m => 3, 7
   cycle shift by m between 5 and 3
   => 2, 3, 5, 7

我不希望任何人想出这个在接受采访时没有被允许研究，虽然:)

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。