检查给定数组是否可以通过将元素减半来形成 1 到 N 的排列
我们的目的是确定对数组中包含的每个项目执行多次除法是否会创建一个从 1 到 N 的整数列表，且没有任何重复项。如果这项工作取得成功，则表明我们的调查目标圆满完成。本质上，确定将给定数组中提供的所有元素除以二是否会产生完全由 1 到 N 之间的非重复值组成的排列是我们工作的主要重点。确认后，评估我们的论文是下一个合乎逻辑的步骤。
语法
在深入研究我们提出的解决方案之前，我们必须粗略地了解即将实施的方法的语法。
bool canBePermutation(vector& arr) { // Implementation goes here }
算法
为了解决这个问题，让我们利用下面逐步介绍的算法来进行 -
要跟踪数组中观察到的组件，请先启动一个集合或哈希集。然后，遍历该数组中存在的每个元素。
为了获得 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 << "给定的数组可以转换为排列。";
} else {
std::cout << "给定的数组不能转换为排列。";
}
return 0;
}
输出
给定的数组不能转换为排列。
解释
方法 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 << "给定的数组可以转换为排列。";
} else {
std::cout << "给定的数组不能转换为排列。";
}
return 0;
}
输出
给定的数组可以转换为排列。
解释
按照方法 2(排序方法)，我们首先按升序排列原始输入数组，然后再继续进行代码例程检查。随后，代码对上述数组中的每个元素进行多次迭代，同时检查它们是否可以被二整除，直到它们达到根据新排序的索引值位置范围确定的指定值和假定值。如果在一次这样的迭代过程中，存在任何不符合这些预定义关键条件的情况，则我们的代码将结果描述为"false"，这表示无法实现将此数组转换为相应的顺序排列。相反，每个符合条件的元素都会产生"true"的结果，从而为我们的数组改组目标带来可行的积极方向。
结论
在本文中，我们深入研究了验证给定数组是否可以通过将其元素减半来转换为包含从 1 到 N 的数字的排列这一挑战。我们为读者提供了有效解决此问题的大纲、语法和算法程序。此外，我们还提供了两种可行的方法以及完整的 C++ 可执行代码示例。通过应用本文重点介绍的基于集合的技术或排序策略，读者可以令人满意地确定任何给定的数组是否符合合法排列的所有必要条件。
