在O(N)时间和O(1)空间中分离数组的奇偶位置

Question

给定一个数组a= {1,2,3,4,5,6,7,8}

我们应该将所有奇数位元素(1，3，5，7)放在一起，将偶数位元素(2，4，6，8)放在一起，同时保持顺序。

输入: 1,2,3,4,5,6,7,8。输出: 1,3,5,7,2,4,6,8。

更新：(示例2)示例2: 3, 54，77，86，45，2，25,100输出: 3，77，45，25，54，86，2,100

限制条件: O(N)时间复杂度和O(1)空间复杂度。

我的方法是: 1.像在(快速排序分区)中那样对它进行分区问题:不保留顺序。( 1,7,3,5,4,6,2,8) -O(N)时间复数2.将奇数元素放到正确的位置并移位所有其他元素:问题:对于每个元素，问题是O(N)，移位需要另一个O(N)。因此，时间复杂度变为O(N^2)

是否存在O(N)时间复数和O(1)空间复数解？

Answer 1

请注意，排序后的索引将是I[] = {0, 2，4，6,1,3,5,7}，I1 =2，I2 =4，I4 =1，循环结束。I3 = 6，I6 = 5，I5 = 3，周期结束。这里的问题是，如果事先不知道n，那么即使可以即时计算Ii (Ii = (2*i < n)？2*i：(2*i-n) | 1；)，问题是跟踪哪些周期已经被处理，这可能需要O(n)空间。

对于8个元素，它是两个周期，每个周期3个元素：

             0 1 2 3 4 5 6 7
       I[] = 0 2 4 6 1 3 5 7

   t = a[1]  2
a[1] = a[2]  1 3 3 4 5 6 7 8 
a[2] = a[4]  1 3 5 4 5 6 7 8
a[4] = t     1 3 5 4 2 6 7 8
   t = a[3]  4
a[3] = a[6]  1 3 5 7 2 6 7 8
a[6] = a[5]  1 3 5 7 2 6 6 8
a[5] = t     1 3 5 7 2 4 6 8

对于12个元素，它只是10个元素的一个循环

               0  1  2  3  4  5  6  7  8  9 10 11  
         I[] = 0  2  4  6  8 10  1  3  5  7  9 11

    t = a[ 1]  2
a[ 1] = a[ 2]  1  3  3  4  5  6  7  8  9 10 11 12
a[ 2] = a[ 4]  1  3  5  4  5  6  7  8  9 10 11 12
a[ 4] = a[ 8]  1  3  5  4  9  6  7  8  9 10 11 12
a[ 8] = a[ 5]  1  3  5  4  9  6  7  8  6 10 11 12
a[ 5] = a[10]  1  3  5  4  9 11  7  8  6 10 11 12
a[10] = a[ 9]  1  3  5  4  9 11  7  8  6 10 10 12
a[ 9] = a[ 7]  1  3  5  4  9 11  7  8  6  8 10 12
a[ 7] = a[ 3]  1  3  5  4  9 11  7  4  6  8 10 12
a[ 3] = a[ 6]  1  3  5  7  9 11  7  4  6  8 10 12
a[ 6] = t      1  3  5  7  9 11  2  4  6  8 10 12

对于27个元素，它是3个周期，从1、3和9开始。

Answer 2

这只是一个部分答案。

下面是数组前半部分的executable pseudocode：

def magic_swap(arr):
    mid = len(arr) / 2 + (1 if len(arr) % 2 == 1 else 0)

    for i in range(1, mid):
        arr[i], arr[i*2] = arr[i*2], arr[i]

下半场是最棘手的部分。如果我弄清楚了，我会更新这个答案。

对于想要弄清楚这一点的人来说，以下是前几个数组大小的结果：

请注意，当n为奇数时，大小为n和n+1的数组在这种方法中总是具有相同的交换顺序。

[1, 2]
[1, 3, 2]
[1, 3, 2, 4]
[1, 3, 5, 4, 2]
[1, 3, 5, 4, 2, 6]
[1, 3, 5, 7, 2, 6, 4]
[1, 3, 5, 7, 2, 6, 4, 8]
[1, 3, 5, 7, 9, 6, 4, 8, 2]
[1, 3, 5, 7, 9, 6, 4, 8, 2, 10]
[1, 3, 5, 7, 9, 11, 4, 8, 2, 10, 6]
[1, 3, 5, 7, 9, 11, 4, 8, 2, 10, 6, 12]
[1, 3, 5, 7, 9, 11, 13, 8, 2, 10, 6, 12, 4]
[1, 3, 5, 7, 9, 11, 13, 8, 2, 10, 6, 12, 4, 14]
[1, 3, 5, 7, 9, 11, 13, 15, 2, 10, 6, 12, 4, 14, 8]
[1, 3, 5, 7, 9, 11, 13, 15, 2, 10, 6, 12, 4, 14, 8, 16]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 10, 6, 12, 4, 14, 8, 16, 2]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 10, 6, 12, 4, 14, 8, 16, 2, 18]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 6, 12, 4, 14, 8, 16, 2, 18, 10]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 6, 12, 4, 14, 8, 16, 2, 18, 10, 20]

Answer 3

有了O(1)和O(n)的限制，这个问题似乎相当困难。

我能找到的最佳匹配是一篇Stable minimum space partitioning in linear time文章，其中他们提出了一个稍微更一般的问题的解决方案。然而，他们的算法很复杂，(IMHO)在实践中不适用。

除非这是一个理论问题，否则我建议分别放宽对O(logN)和O(NlogN)的限制，并使用简单的“稳定分区”算法(更新)：

#inplace reverse block [begin,end) in list l
#O(|end-begin|)
def reverse(l, begin, end):
    p = begin
    q = end - 1
    while p < q:
        l[p], l[q] = l[q], l[p]
        p = p + 1
        q = q - 1

#inplace swaps blocks [begin, mid) and [mid, end) and
#returns a new pivot (dividing point)
#O(|end-begin|)
def swap(l, begin, mid, end):
    reverse(l, begin, mid)
    reverse(l, mid, end)
    reverse(l, begin, end)
    return (end - (mid - begin))

#recursive partitioning: partition block [begin, end) into
#even and odd blocks, returns pivot (dividing point)
##O(|end-begin|*log|end-begin|)
def partition(l, begin, end):
    if end - begin > 1:
        mid = (begin + end) / 2
        p = partition(l, begin, mid)
        q = partition(l, mid, end)
        mid = swap(l, p, mid, q)
        return mid
    return begin if l[begin] % 2 == 0 else begin + 1

def sort(l):
    partition(l, 0, len(l))
    return l

print sort([1,2,3,4,5,6,7,8])

更新。对于更新的问题，文章是直接匹配的。因此，除非有什么技巧可以滥用元素的数值性质，否则我们没有一个简单的解决方案。