所以我必须将数组旋转一个位置但不分配数组以外的额外 space 。这是一个正确的解决方案吗？

Question

这是我的解决方案。这是正确的吗？忽略 bits/stdc++.h 等。我只想知道它是否只使用分配给向量的 space。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cout << "Size of array?\n";
    cin >> n;
    int x[n];
    for (int i = 0; i < n; i++) {
        cout << "Input x[" << i << "]:\n";
        cin >> x[i];
    }
    for (int i = 0; i < n; i++) {
        cout << x[i] << "; ";
    }
    for (int i = 1; i<n; i++) {
        swap(x[0],x[i]);
    }
    for (int i = 0; i < n; i++) {
        cout << x[i] << "; ";
    }
}

Answer 1

对于像这样的初学者可变长度数组

int n;
cout << "Size of array?\n";
cin >> n;
int x[n];

不是标准的 C++ 功能。相反，您应该使用标准容器 std::vector<int>.

要旋转数组或 std::vector<int> 类型的对象，您可以使用标准算法 std::rotate。

至于你的代码，如果你想向左旋转数组，那么这个循环

for (int i = 1; i<n; i++) {
        swap(x[0],x[i]);
}

应该这样写

for (int i = 1; i<n; i++) {
        swap(x[i-1],x[i]);
}

否则你的循环将数组向右旋转。

这是一个演示程序。

#include <iostream>
#include <utility>
#include <vector>

int main() 
{
    std::vector<int> v = { 1, 2, 3, 4, 5 };

    for ( const auto &item : v )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';
    
    for ( size_t i = 1; i < v.size(); i++ )
    {
        std::swap( v[i-1], v[i] );
    }
    
    for ( const auto &item : v )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';
    
    
    return 0;
}

程序输出为

1 2 3 4 5 
2 3 4 5 1

这是一个演示程序，其中使用了标准算法 std::rotate。

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

int main() 
{
    std::vector<int> v = { 1, 2, 3, 4, 5 };

    for ( const auto &item : v )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';
    
    std::rotate( std::begin( v ), std::next( std::begin( v ) ), std::end( v ) );
    
    for ( const auto &item : v )
    {
        std::cout << item << ' ';
    }
    std::cout << '\n';
    
    
    return 0;
}

程序输出同上图

1 2 3 4 5 
2 3 4 5 1

所以我必须将数组旋转一个位置但不分配数组以外的额外 space 。这是一个正确的解决方案吗？

So I have to rotate an array by one position but withou allocating extra space other than the array. Is this a correct solution?

c++

arrays

algorithm

for-loop

rotation