什么是反转数组

反转数组就是把数组里的元素反过来存储。

比如原来的数组是：1，4，2，3

倒转过以后的数组就是：3，2，4，1

这是HackerRank的数据结构部分的第一道题，在讨论区发现了这四种解法，很有意思。

方法一：

思路是：第一项和最后一项互换；第二项与倒数第二项互换；第三项与倒数第三项互换；以此类推，直到换到中间。

时间复杂度是O（n），因为对于有n个元素的数组a，需要交换n/2次。

空间复杂度是O（1），因为只开辟了2个int的空间。

vector<int> reverseArray(vector<int> a) {
    int temp = 0;
    int n = a.size();
    for (int i = 0; i < n/2; ++i) {
        temp = a[n-i-1];
        a[n-i-1] = a[i];
        a[i] = temp;
    }
    return a;
}

方法二：

思路是：新建一个数组b，从后往前遍历数组a，把遍历到的元素加到数组b的后面。

时间复杂度是O（n），需要遍历n次。

空间复杂度是O（n），因为要开辟与输入的数组一样大的空间。

vector<int> reverseArray(vector<int> a) {
    vector<int> b;
    for(vector<int>::iterator x = a.end()-1; x >= a.begin(); x--)
        b.push_back(*x);
    return b;
}

方法三：

这是一个神奇的思路，用的是C++11标准中，vector新的初始化方式。

直接返回一个新的vector，初始化的内容就是数组a从右到左的值。

vector<int> reverseArray(vector<int> a)
{
    return {a.rbegin(), a.rend()};
}

方法四：

这个是使用C++STL库里的reverse函数，需要包含<algorithm>头文件。

vector<int> reverseArray(vector<int> a)
{
    reverse(a.begin(),a.end());
    return a;
}

运行时间比较

同一段程序在不同性能的电脑上运行，运行时间的毫秒数是不同的，但运行时间的CPU Tick数是相同的。所以用CPU Tick数来比较运行时间。

int main( void )    
{    
    int tick=0;
    vector<int> a,b;
    for(int i=1;i<=3000000;i++)   //给数组3000000个元素
    {
        a.push_back(i);           //给数组赋初值
    }
    tick=clock();                 //记录一下反转数组之前的Tick数
    b=reverseArray(a);            //执行反转数组操作
    tick=clock()-tick;            //记录一下反转数组用了多少个Tick
    printf("%d Tick",tick);       //显示反转数组用了多少个Tick
    return 0;
} 

使用上面四种反转数组的方法，在n=3000000的情况下测试，得到的结果是这样的：