在 O(n) 时间复杂度下反转数组

C++C++Beginner
立即练习

💡 本教程由 AI 辅助翻译自英文原版。如需查看原文,您可以 切换至英文原版

介绍

在本实验中,你将学习如何使用 C++ 编程语言中的不同技术来反转数组。数组反转意味着改变数组的顺序,使数组的最后一个元素变为第一个,而第一个元素变为最后一个。本实验将教你如何使用不同的方法实现数组反转,包括使用 for 循环、内置函数、指针、递归以及用户自定义函数。


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("`C++`")) -.-> cpp/BasicsGroup(["`Basics`"]) cpp(("`C++`")) -.-> cpp/ControlFlowGroup(["`Control Flow`"]) cpp(("`C++`")) -.-> cpp/FunctionsGroup(["`Functions`"]) cpp(("`C++`")) -.-> cpp/AdvancedConceptsGroup(["`Advanced Concepts`"]) cpp(("`C++`")) -.-> cpp/IOandFileHandlingGroup(["`I/O and File Handling`"]) cpp/BasicsGroup -.-> cpp/arrays("`Arrays`") cpp/ControlFlowGroup -.-> cpp/for_loop("`For Loop`") cpp/ControlFlowGroup -.-> cpp/while_loop("`While Loop`") cpp/FunctionsGroup -.-> cpp/recursion("`Recursion`") cpp/AdvancedConceptsGroup -.-> cpp/pointers("`Pointers`") cpp/IOandFileHandlingGroup -.-> cpp/output("`Output`") cpp/IOandFileHandlingGroup -.-> cpp/files("`Files`") subgraph Lab Skills cpp/arrays -.-> lab-96214{{"`在 O(n) 时间复杂度下反转数组`"}} cpp/for_loop -.-> lab-96214{{"`在 O(n) 时间复杂度下反转数组`"}} cpp/while_loop -.-> lab-96214{{"`在 O(n) 时间复杂度下反转数组`"}} cpp/recursion -.-> lab-96214{{"`在 O(n) 时间复杂度下反转数组`"}} cpp/pointers -.-> lab-96214{{"`在 O(n) 时间复杂度下反转数组`"}} cpp/output -.-> lab-96214{{"`在 O(n) 时间复杂度下反转数组`"}} cpp/files -.-> lab-96214{{"`在 O(n) 时间复杂度下反转数组`"}} end

创建一个新的 C++ 文件

~/project 目录下通过运行以下命令创建一个名为 reverse_array.cpp 的新 C++ 文件:

touch ~/project/reverse_array.cpp

使用 for 循环反转数组

以下代码展示了如何使用 for 循环反转数组:

#include <iostream>
using namespace std;
void reverseArray(int arr[], int size){
    for(int i=0;i<size/2;i++){
        int temp = arr[i];
        arr[i] = arr[size-i-1];
        arr[size-i-1] = temp;
    }
}
int main(){
    int arr[]={1,2,3,4,5};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Original Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    reverseArray(arr,size);
    cout<<"Reversed Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}

要编译并运行代码,请使用以下命令:

g++ reverse_array.cpp -o reverse_array
./reverse_array

使用内置函数反转数组

以下代码展示了如何使用 C++ 内置函数反转数组:

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int arr[]={1,2,3,4,5};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Original Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    reverse(arr,arr+size);
    cout<<"Reversed Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}

要编译并运行代码,请使用以下命令:

g++ reverse_array.cpp -o reverse_array
./reverse_array

使用用户自定义函数反转数组

以下代码展示了如何定义一个用户自定义函数来反转数组:

#include <iostream>
using namespace std;
void reverseArray(int arr[], int size){
    for(int i=0;i<size/2;i++){
        int temp = arr[i];
        arr[i] = arr[size-i-1];
        arr[size-i-1] = temp;
    }
}
int main(){
    int arr[]={1,2,3,4,5};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"Original Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    reverseArray(arr,size);
    cout<<"Reversed Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}

要编译并运行代码,请使用以下命令:

g++ reverse_array.cpp -o reverse_array
./reverse_array

使用指针反转数组

以下代码展示了如何使用指针反转数组:

#include <iostream>
using namespace std;
void reverseArray(int *arr, int size){
    int *first = arr, *last = arr + size - 1;
    while(first < last){
        int temp = *first;
        *first = *last;
        *last = temp;
        first++;
        last--;
    }
}
int main(){
   int arr[] = {1, 2, 3, 4, 5};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Original Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
   reverseArray(arr, size);
   cout<<"Reversed Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
   return 0;
}

要编译并运行代码,请使用以下命令:

g++ reverse_array.cpp -o reverse_array
./reverse_array

使用递归反转数组

以下代码展示了如何使用递归反转数组:

#include <iostream>
using namespace std;
void reverseArray(int arr[], int start, int end){
    if(start >= end)
        return;
    int temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
    reverseArray(arr,start+1,end-1);
}
int main(){
   int arr[] = {1, 2, 3, 4, 5};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Original Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
   reverseArray(arr,0,size-1);
   cout<<"Reversed Array: ";
    for(int i=0;i<size;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
   return 0;
}

要编译并运行代码,请使用以下命令:

g++ reverse_array.cpp -o reverse_array
./reverse_array

总结

恭喜!你已经完成了「在 O(n) 时间复杂度下反转数组」的实验。你可以在 LabEx 上练习更多实验来提升你的技能。

您可能感兴趣的其他 C++ 教程