检查给定数组是否可以通过将元素减半变成 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++ 可执行代码示例。通过应用本文中突出显示的基于集合的技术或排序策略，读者可以令人满意地确定任何给定数组是否符合合法排列的所有必要条件。