检查给定的数组是否可以通过将元素减半来构成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中文网其他相关文章！