檢查給定陣列是否可以透過將元素減半變成 1 到 N 的排列

---

我們的目的是確定是否可以透過對陣列中每個元素進行多次除法來建立一個不包含任何重複值的從 1 到 N 的整數列表。如果成功完成此任務，則表示我們已經令人滿意地完成了調查目標。從本質上講，確定將給定陣列中所有元素都除以二是否會產生完全由 1 到 N 之間的非重複值組成的排列構成了我們工作的主要重點。確認後，評估我們的論點將成為下一步的邏輯步驟。

語法

在深入研究我們提出的解決方案之前，我們必須對即將實施的方法的語法有一個粗略的瞭解。

bool canBePermutation(vector& arr)
{
   // Implementation goes here
}

演算法

為了解決這個問題，讓我們按照以下步驟逐步使用概述的演算法：

• 為了跟蹤在陣列中觀察到的元素，首先初始化一個集合或雜湊集合。然後，遍歷陣列中存在的每個元素。

• 為了獲得 1 到 N 之間的整數，需要多次將每個元素除以二。

• 檢查結果值是否已存在於集合中。如果是，則返回 false，因為我們在排列中不能有重複項。

• 為了使陣列有資格成為有效的排列，每個元素都必須滿足上述條件。假設該標準完全得到滿足，則可以透過提供 true 的返回值來確認其資格，這可以被認為是適當的行動方案。

方法

為了有效地解決這個問題，探索不同的策略可能會有所幫助。我將介紹兩種可能的方法：

方法 1：基於集合的方法

建立一種高效的方法需要使用細緻的技術，例如使用建立的集合來實現跟蹤系統以記錄整個過程中遇到的元素。它涉及透過除法過程迭代地評估每個元素，確保其結果值僅落在 1 到 N 範圍值之間，然後在將新觀察到的元素附加到跟蹤集合之前，對跟蹤集合進行檢查，然後如果存在任何異常則返回 false，否則在所有值都透過需要評估檢查的組合後返回 true。

示例

#include <iostream>
#include <vector>
#include <unordered_set>

bool canBePermutation(std::vector<int>& arr) {
   std::unordered_set<int> seen;
   
   for (int num : arr) {
      while (num > 0 && num != 1) {
         if (seen.find(num) != seen.end())
            return false;
         
         seen.insert(num);
         num /= 2;
      }
      
      if (num == 0)
         return false;
   }
   
   return true;
}

int main() {
   std::vector<int> arr = {4, 2, 1, 3};
   
   if (canBePermutation(arr)) {
      std::cout << "The given array can be transformed into a permutation.";
   } else {
      std::cout << "The given array cannot be transformed into a permutation.";
   }
   
   return 0;
}

輸出

The given array cannot be transformed into a permutation.

解釋

方法 1 的第一步是設定一個無序集合來跟蹤陣列中存在的元素。然後，這種編碼方法繼續遍歷該陣列中的每個元素，透過每次將它們除以二來反覆將它們減少為 1 到 N 之間的整數。在這些迭代過程中，會檢查是否已經在同一集合中建立了專案；從而嘗試避免僅僅由於重複而導致的重複排列。在檢測到由於這些重複排列產生的重複項時，將返回 false，就像當所有內容在沒有重複完成的情況下檢查透過時一樣 - 代替返回 true - 在指示給定集合是否可以移動到其相應的排列的同時，透過減半來最小化其元件。

方法 2：排序方法

升序排序有助於檢測陣列中的每個元素是否可以在排序列表中呈現其匹配值。如果這些元素中的任何一個都不滿足此標準，我們的輸出將產生 false；但是，如果所有元素都透過此測試，則它將返回 true。

示例

#include <iostream>
#include <vector>
#include <algorithm>

bool canBePermutation(std::vector<int>& arr) {
   std::sort(arr.begin(), arr.end());

   for (int i = 0; i < arr.size(); i++) {
      int expected = i + 1;
      while (arr[i] > 0 && arr[i] != expected)
         arr[i] /= 2;

      if (arr[i] != expected)
         return false;
   }
   
   return true;
}

int main() {
   std::vector<int> arr = {4, 2, 1, 3};
   
   if (canBePermutation(arr)) {
      std::cout << "The given array can be transformed into a permutation.";
   } else {
      std::cout << "The given array cannot be transformed into a permutation.";
   }
   
   return 0;
}

輸出

The given array can be transformed into a permutation.

解釋

根據方法 2（排序方法），我們首先對原始輸入陣列進行升序排列，然後再繼續進行程式碼例程檢查。然後，程式碼對上述陣列的每個元素進行各種迭代，同時檢查它們是否可以被二整除，直到它們達到在其新排序位置索引值範圍內建立的指定和假定的值。如果在一個這樣的迭代輪次中存在任何不符合這些預定義關鍵條件的情況，那麼我們的程式碼將結果界定為“false”，這表示無法實現將此陣列轉換為相應的順序排列。同時，另一方面，每個符合條件的元素都會產生“true”的結果，從而為我們的陣列重排目標帶來可行的積極方向。

結論

在這篇文章中，我們深入探討了驗證給定陣列是否可以透過將其元素減半轉換為包含從 1 到 N 的數字的排列的挑戰。我們為讀者提供瞭解決此問題的有效概述、語法和演算法程式。此外，我們還提供了兩種可行的方法以及完整的 C++ 可執行程式碼示例。透過應用本文中突出顯示的基於集合的技術或排序策略，讀者可以令人滿意地確定任何給定陣列是否符合合法排列的所有必要條件。