数组的就地排列遵循此规则

这是可能的,但它是非常复杂的!一个更简单的O(nlogn)和O(1)空间解决方案在代码和缓存方面可能更好。

我们会解决一个与你不同的问题,但一旦我们解决了这个问题,你的问题就微不足道了。

将数组视为

b1, a1, b2, a2, ..., bn, an

你必须把这个转换成

a1, a2, ..., an, b1, b2, ..., bn

使用指数1到2n,

我们看到这是由

i -> (n+1)*i (mod 2n+1).

O(nlogn)时间O(1)空间解决方案

我们可以用分而治之的方法。

首先是一些接近n/2转换的m

b1, a1, ..., bn , an

到

a1,a2,...am, b1,b2, ..bm, a(m+1), ..., an, b(m+1), ... , bn

通过递归地应用到前2米元素,然后应用到其余元素。

现在我们需要做的就是将中间的数组循环移动m个点(这可以在o(n)时间和o(1)空间中完成)。

给予

a1, a2, .., am , a(m+1), ..., an, b1, b2, ..., bm, b(m+1), ..., bn.

当然,正如ivlad指出的,这需要O(logn)堆栈空间。我们可以通过以下步骤来解决这个问题:

我们有:

b1 a1, b2 a2, .. bm am, b(m+1) a(m+1), ..., bn an

现在交换数组后半部分中的对

b1 a1, b2 a2, .. bm am, a(m+1) b(m+1), ..., an bn

现在循环移动奇数位置的元素: b1, b2, .., bm, a(m+1), a(m+2) ..., a(n).

这给了

a(m+1) a1, a(m+2) a2, ..., a(2m) am, a(2m+1) b(m+1),...,an b(n-m), b1 b(n-m+1),...,bm bn

现在再次交换数组的后一部分

a(m+1) a1, a(m+2) a2, ..., a(2m) am, b(m+1) a(2m+1),...,b(n-m) an,b(n-m+1) b1,..., bn bm

现在递归求解第一部分和第二部分给出

[a1 a2 ... am][a(m+1) ... a(2m)]   [a(2m+1) ...an b1 b2 .. bm][b(m+1) ... bn]

无论2M>=N与否,这都有效。

所以,这是O(nlogn)时间和O(1)空间算法。

O(N)时间O(1)空间解。

使用的想法与以下文章中使用的想法类似: A simple in-place algorithm for Inshuffle .

你需要阅读那篇论文才能理解下面的内容。我建议你也阅读: How to master in-place array modification algorithms?

这基本上就是上面这篇文章所解决的逆排列。

当2n+1是3的幂(比如说3^m)时,就足以解决这个问题,因为我们可以在这之后使用分而治之(比如o(nlogn)解决方案)。

现在2n+1和n+1是相对质数,所以工作模为3^m,我们看到n+1 必须 成为2的力量。(再看那篇论文,看看为什么:基本上,任何数模3^m,相对于3^m是2的幂,同样是模3^m)。

假设n+1=2^k(我们还不知道k,注意这是3^m的模)。

求k的一种方法,计算n+1模3^m的幂,直到它变成1。这给了我们K(最多是O(N)时间)。

现在我们可以看到排列的循环(参见上面的paper/stackoverflow链接了解它是什么)开始于

2 ^ a* 3 ^ b

其中0<=a<k和0<=b<m。

所以你从每一对(A,B)开始,遵循排列的循环,这给了一个O(N)时间,就地算法,因为你接触每一个元素的次数不超过一个常数!

这有点简短!!)如果你需要更多信息,请告诉我。

你所得到的是一个n x 2矩阵,用一维数组表示,你想把它转换成一个2x n数组。

例如,您的列表:

一 _一 ,B _一 A _二 ,B _二 ,…一 _n ,B _n

也可以用矩阵表示:

X _1,1 ,X _1,2 ,X _2,1 ,X _2,2 ,…X _n,1 ,X _n,2

你想转置成:

X _1,1 ,X _2,1 ,…X _n,1 ,X _1,2 ,X _2,2 ,…X _n,2

这个 in place matrix transposition algorithm 会完成任务的。

编辑

好的,让我把它拼出来。尝试以下代码位:

i = 0                /* linear array index */
do j = 1 to c        /* j = 1 to virtural columns */
  do k = 1 to r      /* k = 1 to virtural rows */
    i = i + 1
    sp = (k - 1) * c + j
    do while sp < i
      ct = (sp - 1) % r + 1
      rt = sp - (ct - 1) * r
      sp = (rt - 1) * c + ct
    end
    if i \= sp then say 'swap('i',' sp')'   /* swap elements */
  end
end

这将打印出需要交换的数组元素。这将适用于线性数组中表示的任何大小的矩阵,其中元素按列排列,然后按行排列。使用n x 2 martix,元素排列如下:

X _1,1 ,X _1,2 ,X _2,1 ,X _2,2 ,…X _n,1 ,X _n,2

该算法打印出需要交换的元素,以生成一个按如下顺序排列的数组:

X _1,1 ,X _2,1 ,…X _n,1 ,X _1,2 ,X _2,2 ,…X _n,2

例如,从r=4,c=2开始,数组:

 A1, B1, A2, B2, A3, B3, A4, B4

需要以下交换:

swap(2, 3)
swap(3, 5)
swap(4, 7)
swap(6, 7)

成为:

 A1, A2, A3, A4, B1, B2, B3, B4

该算法在空间和时间上都是有效的。

海上舞台

我的O-foo不太好,但我会试一试…

矩阵包含两列(“a”和“b”)和“m”行。将其表示为 一个线性阵列,我们需要2米的元素。让我们调用这个数字n(线性数组的大小)。

该算法有两个迭代循环,一个用于“r”(行),另一个用于“c”(列)。 总的迭代次数是r*c,在我们的例子中是2 m=n,到目前为止还不错。

外卡是内在的 DO WHILE 循环。对于给定的行数,它需要多少次迭代? 答案可能是:相当多。 根据一些经验结果(如下所示),它看起来像 做而不做 迭代 当“c”=2(或可能是“c”的任何值)时,是涉及“r”的复杂函数。 我没有足够的O-foo来精确地计算出这个函数是什么。 但是,它不应该比n更糟。 ^三 (一个完整的“追踪”矩阵,n ^二 时代 每个元素,n)。理论上不是一幅好照片。所以我想这就是O(N) ^三 )?这可能是 一种非O(N)算法,但在实际应用中,由于 经验数据如下。我有点迷路了-欢迎评论!

关于 做而不做 但是循环:它使用基于整数的简单变量数学(没有数组 需要参考)。如果你是非线性的,这有 成为最便宜的地方!

需要多少个交换?交换次数限制为每次迭代通过外部 两个循环,最多N次。交换次数与O(N)性能一致。

我的猜测是这是一个非O(N)算法,但似乎有合理的行为 对于中等大小的2列矩阵。

以下是各种2列矩阵大小的一些经验结果:

      Rows Loops per row
========== =============
       500             9
     1,000            19
     1,500            21
     2,000            12
     2,500            18
     3,000            23
     3,500            26
 1,000,000            30
 2,000,000            40
 3,000,000            45
10,000,000            59
20,000,000            39
30,000,000            60

“每行循环数”随着行数的增加而增加,但不会以惊人的速度增长。危险的是它会达到指数级的“最佳”位置——但我不知道它是否真的有这种潜力。

我对MGCCL的建议是在行计数范围内对该算法进行基准测试 在他的应用中很典型,然后决定它是否会产生一个可接受的性能相对于其他 算法基准。Big-O分析 很有趣,但是在一个操作数据范围内的结果才是重要的。

最后一脚在罐子上: 为什么这个算法有效?

转置以线性形式表示的矩阵:

给定矩阵x有m行和n列。

将x按行主顺序排列成一个线性数组。这个 阵列的组织方式如下:

11, 12, 13, ... 1N, 21, 22, 23, ... 2N, ... M1, M2, M3 ... MN

描述线性数组中每个元素的符号 是:

    X[i,r,c] 

where: i is the linear array index for element X 
       r is the row number for element X
       c is the column number for element X. 

用这个符号, 按行主顺序排列的数组可以生成为:

i = 0
for j = 1 to M    /* Row counter */
  for k = 1 to N  /* Column counter */
    i = i + 1     /* array index of element j, k */
    say 'X['i','j',k']'
  end
end

请注意,给定的j(行)和k(列)值,i可计算为:

i = (j - 1) * N + k

矩阵x的转置是通过交换元素构造的。 x[i,r,c]和x[t,c,r]在r和c的范围内。本质上,我们交换 列变量的所有行变量。使用符号 如上所述,这相当于交换线性阵列元素:

    exchange(X[i,r,c], X[t,c,r])

where: i = (r - 1) * N + c
       t = (c - 1) * M + i

转置矩阵所需的交换次数将小于 m*n是因为最多需要一次交换才能将一个元素放入其正确的元素中。 位置。在某些情况下,不需要交换,因为 元素已“就位”。例如x的第一个和最后一个元素 不需要交换。

通过增加i继续通过线性阵列,我们知道只要 所有的交换都不涉及I>T,矩阵将在其中 索引小于或等于i的所有元素的列主顺序。

每当I>T时,这意味着之前在指数T进行了交换。 如上文所示,在t处交换元素。 在某个新的位置t’。给定一个索引t,我们可以计算行主索引t' 以及与之关联的行和列编号,如下所示:

 c' = (t - 1) % M + 1
 r' = t - (c' - 1) * M
 t' = (r' - 1) * N + c'

同样,如果t'小于i,这意味着这个元素也被交换了,我们必须 继续进行另一轮计算。将t设置为计算的t'并重复。 最终,我会变成 交换可以完成。基本上,我们“追逐”元素的所有 之前的交换,直到我们在i或i的右边找到它为止。 数组。

对线性数组中的每个元素重复此循环,矩阵将 被调换了。

o(1)时间,o(1)额外空间

#include <vector>
#include <iostream>
#include <ctime>
#include <boost/random.hpp>

template <typename T>
class pvec
{
private:
    // Stores values to permute
    std::vector<T> v;

    // Flag; true when permuted; false when not
    bool permuted;

public:
    pvec(size_t size) : v(size), permuted(false) {}

    // Set the permutation flag
    void set_p(bool p) { permuted = p; }

    // When the permuted flag is set, return the permuted element, otherwise
    // return the non-permuted element
    T& operator[](size_t i) { return (permuted ? v[p_ind(i)] : v[i]); }

    // Pass through the size of the vector used
    size_t size() const { return v.size(); }

private:
    // Used to determine the permuted index of a given index
    size_t p_ind(size_t i) const
    {
        return ( i < v.size()/2 ? i * 2 : 2 * (i - v.size()/2) + 1);
    }
};

// Used to display a pvec instance
template <typename T>
std::ostream& operator<<(std::ostream& os, pvec<T>& v)
{
    for (size_t i = 0; i < v.size(); ++i)
        os << (i == 0 ? "<" : ", ") << i << ":" << v[i];
    os << ">";
    return os;
}

int main(int argc, char** argv)
{
    const size_t size = 8;
    pvec<uint32_t> v(size);  // Array containing test values

    // Boost Random Number Library used to generate random values in the test
    // array
    boost::mt19937 rng(std::time(0));
    boost::uniform_int<> dist(0,65536);
    boost::variate_generator<boost::mt19937&, boost::uniform_int<> >
        var(rng, dist);

    // Generate random test values
    for (size_t i = 0; i < size; ++i)
        v[i] = var();

    // Observer original vector
    std::cout << v << std::endl;

    // Set the permutation flag O(1) time
    v.set_p(true);

    // Observe the permuted vector
    std::cout << v << std::endl;

    return 0;
}

输出:

<0:44961, 1:246, 2:54618, 3:41468, 4:12646, 5:21691, 6:26697, 7:36409>
<0:44961, 1:54618, 2:12646, 3:26697, 4:246, 5:41468, 6:21691, 7:36409>

好吧,让我们看看这个例子:

0 1 2 3 4 5 6 7 8 9 10

0 2 4 6 8 10 1 3 5 7 9

结果的前半部分包含元素,其索引为原始索引i的i/2,而另一半是i-n/2+1,其中n是数组中的项数。

这基本上是排序算法的一种特殊情况,只是设置了一个特殊的顺序。

所以这里有一个使用冒泡排序算法对整数数组排序的想法。我们需要的是将偶数值拉到开头,留下奇数值:

0 1 2 3 4 5 6 7 8 9 10
  * *
0 2 1 3 4 5 6 7 8 9 10
      * *
0 2 1 4 3 5 6 7 8 9 10
    * *
0 2 4 1 3 5 6 7 8 9 10
          * *
0 2 4 1 3 6 5 7 8 9 10
        * *
...
0 2 4 6 1 3 5 7 8 9 10
              * *
...
0 2 4 6 8 1 3 5 7 9 10
                  * *

但是,只有在您可以保留索引(即在本例中,索引与数组值相关联)的情况下,这才有效。BubbleSort的性能为O(n^2),内存使用率为1。

它不能在O(n)时间和1内存中完成[编辑:仅使用通用排序算法!],在o(nlog n)中执行的最佳通用排序算法:

http://en.wikipedia.org/wiki/Sorting_algorithm

要解决您的问题,最好的方法是生成一系列符合您标准的索引:

size_t* indices = new size_t[n]; 

// n is the number of items in the original array
for (int i = 0; i < n; i++)
{
    if (i < n / 2)
    {
       indices[i] = i * 2;
    }
    else
    {
       indices[i] = i - n / 2 + 1;
    }
}

然后简单地使用它将原始数组中的项映射到新位置:

// i is the new index here, which makes it appear as if ValuesArray has been sorted
Type* getOddEvenValue(size_t newIndex)
{
     // ValuesArray and indices should be available in this scope, of course
     return ValuesArray[indices[newIndex]];
}

这个东西可以在O(N)中运行,但也需要O(N)内存。但是,如果sizeof类型比sizeof int大得多,那么它仍然是内存使用量的增加(而不是复制类型对象)。

[编辑2]

除了需要将原始向量复制到类的实例中的漂亮的oop代码anddo之外,您可以简单地编写一个函数:

 size_t permuted_index(size_t i, size_t vecSize)
 {
    return ( i < vecSize/2 ? i * 2 : 2 * (i - vecSize/2) + 1);
 }

当你需要得到排列值的时候就使用它。实际上,这只需要O(n)次时间,因为对于给定的向量(至少在一个完整的“for each”循环中),Permutted_索引的计算结果不会超过N次。