查找数组中不存在的给定大小的二进制字符串的任何排列
在此问题中，我们需要从数组中查找所有缺失的长度为 N 的二进制字符串。我们可以通过查找长度为 N 的二进制字符串的所有排列并检查数组中缺少哪些排列来解决问题。在这里，我们将看到迭代和递归方法来解决问题。
问题陈述– 我们给出了一个不同长度的数组 arr[]，其中包含长度为 N 的二进制字符串。我们需要从数组中找到所有缺失的长度为 N 的二进制字符串。
示例
输入– arr = {"111", "001", "100", "110"}, N = 3
输出– [000, 010, 011, 101]
解释– 有 8 个长度为 3 的二进制字符串，因为 23 = 8。因此，它打印缺失的 4 个长度为 3 的二进制字符串3.
输入– str = {'00', '10', '11'}, N = 2
输出– ['01']
解释– 由于数组中缺少'01'，因此它会打印在输出中。
方法 1
在这里，我们将使用迭代方法查找所有可能的长度为 N 的二进制字符串。之后，我们将检查字符串是否存在于数组中。如果没有，我们就打印该字符串。
算法
定义集合并使用 insert() 方法将数组的所有字符串添加到集合中。
用 2N 初始化 total 变量，即长度为 N 的字符串总数
定义"cnt"变量并用零初始化以存储缺失组合的总数。
使用循环进行"总"迭代次数以查找长度为 N 的所有二进制字符串。
在循环中，用空字符串初始化"num"字符串变量。
使用嵌套循环进行总共 N 次迭代，并从最后一次开始迭代以创建长度为 N 的字符串。
使用 find() 方法检查集合是否包含当前字符串。 如果是，则将"cnt"的值增加 1。
如果字符串不在映射中，则将其打印以显示在输出中
如果"cnt"的值等于总数，则表示所有长度为 N 的字符串都存在于数组中并打印"-1"。
示例
#include <bits/stdc++.h>
using namespace std;
// 函数用于打印数组中长度为 N 的二进制字符串的缺失组合
void printMissingCombinations(vector<string> &arr, int N) {
unordered_set<string> set;
// 将所有字符串插入集合中
for (string temp : arr) {
set.insert(temp);
}
// 获取长度为 N 的字符串的总组合数
int total = (int)pow(2, N);
// 存储数组中存在的组合
int cnt = 0;
// 查找所有组合
for (int p = 0; p < total; p++) {
// 初始化空二进制字符串
string bin = "";
for (int q = N - 1; q >= 0; q--) {
// 如果设置了第 q 位，则附加'1'；附加'0'。
if (p & (1 << q)) {
bin += '1';
} else {
bin += '0';
}
}
// 如果组合存在于数组中，则增加cnt
if (set.find(bin) != set.end()) {
cnt++;
continue;
} else {
cout << bin << ", ";
}
}
// 如果数组中存在所有组合，则打印 -1
if (cnt == total) {
cout << "-1";
}
}
int main() {
int N = 3;
vector<string> arr = {"111", "001", "100", "110"};
printMissingCombinations(arr, N);
return 0;
}
输出
000, 010, 011, 101,
时间复杂度 – O(N*2N)，其中 O(N) 用于检查字符串是否存在于数组中，O(2N) 用于查找所有可能的排列。
空间复杂度 – O(N)，因为我们使用集合来存储字符串。
方法 2
在这种方法中，我们演示了使用递归方法查找长度为 N 的所有可能的二进制字符串。
算法
定义集合并将所有数组值插入集合中。
调用 generateCombinations() 函数生成二进制字符串的所有组合
在 generateCombinations() 函数中定义基本情况。如果索引等于 N，则将 currentCombination 推送到列表中。
将"0"或"1"附加到 currentCombination 后，递归调用 generateCombinations() 函数。
获取所有组合后，检查哪些组合存在，哪些组合不在数组中。此外，打印缺失的组合以显示在输出中。
示例
#include <bits/stdc++.h>
using namespace std;
// 生成所有可能二进制字符串组合的函数
void generateCombinations(int index, int N, string currentCombination, vector<string> &combinations) {
// 基本情况：如果已达到所需长度 N，则将组合添加到向量中
if (index == N) {
combinations.push_back(currentCombination);
return;
}
// 通过在当前索引处尝试 0 和 1 来递归生成组合
generateCombinations(index + 1, N, currentCombination + "0", combinations);
generateCombinations(index + 1, N, currentCombination + "1", combinations);
}
// 函数用于在数组中打印长度为 N 的二进制字符串的缺失组合
void printMissingCombinations(vector<string> &arr, int N) {
unordered_set<string> set;
// 将所有字符串插入集合中
for (string str : arr) {
set.insert(str);
}
// 生成长度为 N 的二进制字符串的所有组合
vector<string> combinations;
generateCombinations(0, N, "", combinations);
// 遍历所有组合并检查它是否存在于集合中
for (string str : combinations) {
// 如果组合不存在于集合中，则打印它
if (set.find(str) == set.end()) {
cout << str << endl;
}
}
return;
}
int main(){
int N = 3;
vector<string> arr = {"111", "001", "100", "110"};
printMissingCombinations(arr, N);
return 0;
}
输出
000 010 011 101
时间复杂度 – O(N*2N)
空间复杂度 – O(2N)，因为我们将所有组合存储在数组中。
两种方法使用相同的逻辑来解决问题。第一种方法使用迭代技术来查找长度为 N 的二进制字符串的所有组合，这比第二种方法中使用的递归技术更快。此外，第二种方法比第一种方法消耗更多空间。
