C++算法：按照以下顺序切换数组的顺序：[最后一个元素，第一个元素，倒数第二个元素，第二个元素……]

Question

C++算法：按照以下顺序切换数组的顺序：[最后一个元素，第一个元素，倒数第二个元素，第二个元素……]

3

我应该如何只使用循环来实现这样的功能？

我正在绞尽脑汁，但似乎无法清晰地思考。

这是我想到的，但与要求相去甚远。

for (int i = 0; i < elements; i++)
{
    for (int n = elements; n > 0; --n)
        a[i] = b[n];
}

- Satoshi Hayama

可以原地进行还是需要使用临时变量？使用STL算不算（它们在内部使用循环）。 - graham.reeds

那些都可以，我只是想知道循环算法如何解决这样的问题。 - Satoshi Hayama

6个回答

3

您可以使用计数器i从0到len / 2进行操作，并相应地存储。

伪代码应该类似于此。

len = length of array
counter = 0
For i = 0 to (len / 2):
    a[counter++] = b[len - i]
    a[counter++] = b[0 + i]

- Haris

如果原始数组中有奇数个元素会怎样？ - samgak

2

这会有效吗？如果你能使用另一个数组a，它就变得简单而且不复杂，原始数据来自b

for (int i = 0, i_even = 1, i_odd = 0; i < elements; i++)
{
     if(i % 2 == 0){
         a[i] = b[elements-i_even];
         ++i_even;
     }
     else {
         a[i] = b[i_odd];
         ++i_odd;
}

完整示例：

#include <iostream>
#include <vector>

using namespace std;

vector<int> switched(const vector<int>& b){
    const std::size_t sz = b.size();
    vector<int> a(sz);

    for (int i = 0, i_even = 1, i_odd = 0; i < sz; i++) {
        if(i % 2 == 0) {
            a[i] = b[sz-i_even];
            ++i_even;
        }
        else {
            a[i] = b[i_odd];
            ++i_odd;
        }
    }
    return a;
}

void print(const vector<int>& v){
    for (auto e: v)
        cout << e << " "; cout << endl;
}

int main()
{
    vector<int> b{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    print(b);
    print(switched(b));

    return 0;
}

- WhiZTiM

请注意，任务不是将数组反转。看一下问题标题中的顺序... - leemes

@leemes ...更正...我必须承认Vlad的答案更加流畅。 :-) - WhiZTiM

@WhiZTiM，你的解决方案在处理数组时存在问题。它没有原地修改数组。 - Vlad from Moscow

@VladfromMoscow 这是时空权衡的问题...这是我能想到的唯一的O(n)解决方案{空间开销}。这就是为什么我在我的答案中提到：“..如果你能用另一个数组..”。 - WhiZTiM

1

一个没有使用if的小解决方案。

std::vector<int> a{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
std::vector<int> b;

b.reserve(a.size());
size_t l = a.size() - 1;

for (int i = 0; i < a.size(); ++i)
{
    b.push_back( a[(i / 2) + ((i + 1) % 2) * (l - i)] );
}

for (int i = 0; i < b.size(); ++i)
{
    std::cout << b[i] << "\n";
}

它使用整数算术运算。

- Tunichtgut

0

在我的脑海中，这个工作了：

a[] = b[];
len= lenght of a;

for(int i=0; i<len/2; i++)
{
     int j = 0;
     a[j] = b[len-i];
     j++;
     a[j] = b[i];
}

需要注意的是，这可能会导致奇怪的数组长度问题。

- FruitSokrat

0

另一种方法是倒推。在位置i结束的元素来自哪里？

dest src 
0    0
1    size-1

2    1
3    size-2

4    2
5    size-3

所以如果dest是偶数，那么src=dest/2，如果dest是奇数，则src=size-1-(dest/2)。

这种方法的优点是您不需要为奇数长度的输入编写特殊代码。

- MSalters

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vlad from Moscow · Accepted Answer

这里是你需要的内容

#include <iostream>
#include <algorithm>
#include <iterator>

int main()
{
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    for ( int x : a ) std::cout << x << ' ';
    std::cout << std::endl;

    for ( auto it = std::begin( a ); it != std::end( a ); it == std::end( a ) ? it : ++it )
    {
        it = std::rotate( it, std::prev( std::end( a ) ), std::end( a ) );
    }        

    for ( int x : a ) std::cout << x << ' ';
    std::cout << std::endl;
}

程序的输出为：

0 1 2 3 4 5 6 7 8 9 
9 0 8 1 7 2 6 3 5 4

编译器应支持C++11算法std::rotate。

P.S. 我更改了循环的第三个表达式，使其适用于具有奇数个元素的序列。

另一种方法是使用标准算法std::copy_backward。类似以下方式：

#include <iostream>
#include <algorithm>
#include <iterator>

template <class BidirectionalIterator>
void alternate( BidirectionalIterator first, BidirectionalIterator last )
{
    if ( first != last && first != --last )
    {
        while ( first != last )
        {
            auto value = *last;
            std::copy_backward( first, last, std::next( last ) );
            *first++ = value;
            if ( first != last ) ++first;
        }
    }
}    

int main()
{
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    for ( int x : a ) std::cout << x << ' ';
    std::cout << std::endl;

    alternate( std::begin( a ), std::end( a ) );

    for ( int x : a ) std::cout << x << ' ';
    std::cout << std::endl;
}

程序的输出为：

0 1 2 3 4 5 6 7 8 9 
9 0 8 1 7 2 6 3 5 4