39. 逆转数组（二）
2021-03-30 06:26
标签：数组 空间复杂度 需要 复杂度 交换 void 算法 class ack 一. 问题 给定一个含有 n 个元素的序列 A，将序列中的元素逆转。 二. 思路 在前一篇文章中，我选择用用临时变量，来进行前后元素交换。这种算法的时间复杂度是 O( n )，空间复杂度是 O( 1 )（因为用到了有限个临时变量）。现在我们考虑一种新的算法：用一个栈来读入序列中的元素，再将栈中元素弹出，重新放回序列中。这样就完成了整个序列的逆转。此算法的时间复杂度仍然是 O( n )，但是空间复杂度变为 O( n )（因为栈的大小随着序列长度变化）。 三. 代码实现 代码中有几处需要说明： （1）先声明一个栈用于读入数据。 （2）在读入的时候，用 top()方法，此方法只查看栈顶元素。因此下一步应该将此元素弹出，用到 pop() 方法。 39. 逆转数组（二） 标签：数组 空间复杂度 需要 复杂度 交换 void 算法 class ack 原文地址：https://www.cnblogs.com/Hello-Nolan/p/13586007.html 1 void reverse_array_stack(vectorint>& data) {
2 stackint> temp_data;
3
4 for (auto& i : data) {
5 temp_data.push(i);
6 }
7
8 for (auto& j : data) {
9 j = temp_data.top();
10 temp_data.pop();
11 }
12 }