极客笔记C++ 检查给定的数组是否可以通过将元素减半得到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 << "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.
解释
第一种方法的初始步骤是建立一个无序集合，用于跟踪数组中存在的元素。然后，这种编码方法会迭代遍历数组中的每个元素，通过每次除以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整除，直到它们达到在新排序的索引值范围内的指定值。如果在一次迭代中存在任何不符合这些预定义临界条件的情况，我们的代码将给出一个”false”的结果，表明无法将该数组转化为相应的顺序排列。反之，每个符合条件的元素都将给出一个”true”的结果，为我们重组数组的愿望提供了一个可行的正向方向。
结论
在本文中，我们深入探讨了验证给定数组是否可以通过将其元素减半来转化为由1到N的数字构成的排列的挑战。我们为读者提供了有效解决这个问题的概述、语法和算法过程。此外，我们还提供了两种可行的方法以及完整的可执行C++代码示例。通过应用本文中提到的基于集合的技术或排序策略，读者可以令人满意地确定任何给定数组是否符合合法排列的所有必要条件。