透過在每次從給定陣列插入後重復反轉陣列獲得的陣列

---

陣列插入和反轉是最常見的陣列操作技術之一。陣列操作旨在修改陣列的內容以獲得期望的結果。

問題陳述

給定一個輸入陣列 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)。