通过在每次从给定数组插入后重复反转数组获得的数组

---

数组插入和反转是最常见的数组操作技术之一。数组操作旨在修改数组的内容以获得期望的结果。

问题陈述

给定一个输入数组 A[]。任务是将给定数组的元素插入到现有的数组中，其中输出数组的反转跟随每次插入。

示例 1

Input: A[] = {1,2,3,4,5}
Output: R[] = {5, 3, 1, 2, 4}

解释

最初，输出数组 R[] 为空。

• 插入 1：R[] = {1}

• 插入 2：R[] = {2, 1}

• 插入 3：R[] = {3, 1, 2}

• 插入 4：R[] = {4, 2, 1, 3}

• 插入 5：R[] = {5, 3, 1, 2, 4}

示例 2

Input: A[] = {1, 4, 5, 11}
Output: R[] = {11, 4, 1, 5}

解释

最初，输出数组 R[] 为空。

• 插入 1: R[] = {1}

• 插入 4: R[] = {4, 1}

• 插入 5: R[] = {5, 1, 4}

• 插入 11: R[] = {11, 4, 1, 5}

方法 1：蛮力法

解决该问题的蛮力和最直接的方法是在输出数组中插入一个元素，然后反转数组，然后插入下一个元素。

伪代码

function insertAndReverse(arr)
   result = empty vector
   for i from 0 to arr. size() - 1
      result.insert(result.begin(), arr[i])
      if i is not equal to (arr. size() - 1)
         reverse(result.begin(), result.end())
   return result

示例

以下是该问题蛮力解决方案的 C++ 实现。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> insertAndReverse(vector<int> arr){
   vector<int> result;
   for (int i = 0; i < arr.size(); i++)    {
      result.insert(result.begin(), arr[i]);
      if (i != (arr.size() - 1))        {
         reverse(result.begin(), result.end());
      }
   }
   return result;
}
int main(){
   vector<int> given_array = {1, 2, 3, 4};
   vector<int> result_array = insertAndReverse(given_array);
   // Output the result array
   for (int num : result_array)    {
      cout << num << " ";
   }
   cout << endl;
   return 0;
}

输出

4 2 1 3

时间复杂度 - O(N^2)，因为反转语句的时间复杂度为 O(N)，并且语句位于 for 循环内导致 O(N^2) 时间复杂度。

空间复杂度 - O(N)

方法 2：优化方案

查看结果的模式，可以得出结论，结果数组可以通过交替地从前面和后面向数组添加元素来获得。

可以使用此观察结果获得该问题的优化解决方案。

伪代码

function insertAndReverse(arr):
   result = empty vector
   for i from 0 to arr. size() - 1:
      if i is odd (i & 1 is not 0):
         result.insert(result.begin(), arr[i])
      else:
         result.insert(result.end(), arr[i])
   if arr.size() is odd (arr.size() & 1 is not 0):
      reverse(result.begin(), result.end())
   return result

示例

C++ 实现

在以下程序中，元素交替地推送到数组的前部和后部。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> insertAndReverse(vector<int> arr){
   vector<int> result;
   for (int i = 0; i < arr.size(); i++){
      if(i & 1){
         result.insert(result.begin(), arr[i]);
      } else {
         result.insert(result.end(), arr[i]);
      }
   }    
   if (arr.size() & 1){
      reverse(result.begin(), result.end());
   }
   return result;
}
int main(){
   vector<int> given_array = {1, 2, 3, 4};
   vector<int> result_array = insertAndReverse(given_array);
   // Output the result array
   for (int num : result_array){
      cout << num << " ";
   }
   cout << endl;
   return 0;
}

输出

4 2 1 3

结论

总之，上面解决的问题是一个数组操作问题，可以使用最佳方法解决，每个方法的时间和空间复杂度分别为 O(N)。