代码之家 › 专栏 › 技术社区 › Jon Cage

原地旋转二维矩形阵列

in-place rotation arrays c++

4

Jon Cage · 技术社区 · 16 年前

我有一个像这样的非方形数组:

const int dim1 = 3, dim2 = 4;
int array[12] = { 1, 2, 3, 
                  4, 5, 6,
                  7, 8, 9,
                 10,11,12};

我需要把它转换成:

{3,6,9,12,
 2,5,8,11,
 1,4,7,10}

也就是说,逆时针旋转/洗牌(或者顺时针,算法应该类似)。

算法应该使用最小的空间量。我必须在内存非常有限的环境中旋转图像,因此空间越小越好。速度不是一个大问题。

4 回复 | 直到 16 年前

1

7

Yakov Galka 16 年前

http://en.wikipedia.org/wiki/In-place_matrix_transposition

2

1

Andreas Magnusson 16 年前

x' = x cos f - y sin f
y' = y cos f + x sin f

x' = -y
y' =  x

// this function rotates 90 degrees
point successor(const point &p)
{
  return (-p.y, p.x);
}

// this function rotates 90 degrees in opposite direction
point predecessor(const point &p)
{
  return (p.y, -p.x);
}

void replace_cycle(const point &start)
{
  int data = get_data(start);
  point x = predecessor(start);
  while(x != start)
  {
    set_data(successor(x), get_data(x));
    x = predecessor(x);
  }
  set_data(successor(start), data);
}

void rotate_in_place()
{
  list<point> l;
  find_cycles(l);
  foreach(c in l)
  {
    replace_cycle(c);
  }
}

3

0

kriss 16 年前

4

-1

Wernight 16 年前

// Switch a and b
int a;
int b;
a ^= b;
b ^= a;
a ^= b;

for