檢查給定的數組是否可以透過將元素減半來構成1到N的排列

我們的目的是確定對數組中包含的每個項目執行多次除法是否會創建一個從 1 到 N 的沒有任何重複項的整數列表。這項努力的成功將意味著我們的調查目標圓滿實現。本質上，確定將給定數組中提供的所有元素切割兩個是否會產生完全由 1 到 N 之間的非重複值組成的排列，這是我們工作的主要焦點。確認後，評估我們的論文將成為下一個合乎邏輯的步驟。

文法

在深入研究我們提出的解決方案之前，粗略地了解即將實現的方法的語法非常重要。

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

演算法

為了解決這個問題，讓我們繼續使用下面概述的演算法來逐步進行 -

• 要密切注意數組中觀察到的元件，請從啟動集合或雜湊集開始。然後，迭代該數組中存在的每個元素。

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

• 檢查結果值是否已存在於集合中。如果是，則傳回 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 的初始步驟涉及設定一個無序集來追蹤數組中存在的元素。然後，這種編碼方法會繼續迭代同一數組中的每個元素，每次除以 2，將它們重複減少為 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（排序方法），我們先按升序排列原始輸入數組，然後再進一步進行程式碼例程檢查。程式碼隨後對上述陣列的每個單獨元素執行各種迭代，同時檢查它們是否可被二整除，直到它們達到根據其在新排序的索引值位置範圍內的位置建立的指定和假定值。如果在這樣的一輪迭代中存在任何不符合這些預定義關鍵條件的情況，那麼我們的程式碼將結果描述為“假”，這表示無法實現將此數組轉換為相應的順序排列。同時，相反，每個合規元素都會產生「true」結果，為我們的陣列重組目標提供可行的正向方向。

結論

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

以上是檢查給定的數組是否可以透過將元素減半來構成1到N的排列的詳細內容。更多資訊請關注PHP中文網其他相關文章！