在这个问题中，我们需要从数组中找到长度为N的所有缺失的二进制字符串。我们可以通过找到长度为N的二进制字符串的所有排列，并检查哪些排列在数组中不存在来解决这个问题。在这里，我们将看到迭代和递归的方法来解决这个问题。
问题陈述 – 我们已经给出了一个包含不同长度的二进制字符串的数组arr[]，长度为N。我们需要从数组中找出所有长度为N的缺失二进制字符串。
示例例子
输入 – arr = {“111”, “001”, “100”, “110”}, N = 3
输出 – [000, 010, 011, 101]
Explanation – 有8个长度为3的二进制字符串，因为2的3次方等于8。所以，它打印出长度为3的缺失的4个二进制字符串。
输入 – str = {‘00’, ‘10’, ‘11’}, N = 2
Output – [‘01’]
Explanation – ‘01’在数组中缺失，因此会在输出中打印出来。
方法一
在这里，我们将使用迭代的方法来找到长度为N的所有可能的二进制字符串。之后，我们将检查该字符串是否存在于数组中。如果不存在，我们将打印该字符串。
算法
定义集合并使用insert()方法将数组中的所有字符串添加到集合中。
用2N初始化total变量，其中2N是长度为N的字符串的总数
定义变量 ‘cnt’ 并将其初始化为零，以存储缺失组合的总数。
使用循环来使’总’迭代次数，以找到所有长度为N的二进制字符串。
在循环中，使用空字符串初始化“num”字符串变量。
使用嵌套循环进行总共N次迭代，并从最后一次迭代开始，创建长度为N的字符串。
使用find()方法来检查集合是否包含当前字符串。如果是，则将‘cnt’的值增加1。
如果字符串不在映射中，则打印它以显示在输出中
如果“cnt”的值等于总数，则表示数组中存在所有长度为N的字符串，并打印“-1”。
Example
#include using namespace std;// function to print missing combinations of a binary string of length N in an arrayvoid printMissingCombinations(vector &arr, int N) { unordered_set set; // insert all the strings in the set for (string temp : arr) { set.insert(temp); } // get total combinations for the string of length N int total = (int)pow(2, N); // To store combinations that are present in an array int cnt = 0; // find all the combinations for (int p = 0; p = 0; q--) { // If the qth bit is set, append '1'; append '0'. if (p & (1 arr = {"111", "001", "100", "110"}; printMissingCombinations(arr, N); return 0;}
登录后复制
输出
000, 010, 011, 101,
登录后复制
时间复杂度 – O(N*2N)，其中O(N)用于检查字符串是否存在于数组中，O(2N)用于找到所有可能的排列。
空间复杂度 – O(N)，因为我们使用set来存储字符串。
方法二
在这种方法中，我们展示了使用递归方法来找到长度为N的所有可能的二进制字符串。
算法
定义集合并将所有数组值插入集合中。
调用generateCombinations()函数生成二进制字符串的所有组合
在generateCombinations()函数中定义基本情况。如果索引等于N，则将currentCombination添加到列表中。
在将‘0’或‘1’添加到当前组合后，递归调用generateCombinations()函数。
获取所有组合后，检查哪些组合存在于数组中，哪些不存在。同时，打印出缺失的组合以在输出中显示。
Example
#include using namespace std;// Function to generate all possible combinations of binary stringsvoid generateCombinations(int index, int N, string currentCombination, vector &combinations) { // Base case: if we have reached the desired length N, add the combination to the vector if (index == N) { combinations.push_back(currentCombination); return; } // Recursively generate combinations by trying both 0 and 1 at the current index generateCombinations(index + 1, N, currentCombination + "0", combinations); generateCombinations(index + 1, N, currentCombination + "1", combinations);}// function to print missing combinations of a binary string of length N in an arrayvoid printMissingCombinations(vector &arr, int N) { unordered_set set; // insert all the strings in the set for (string str : arr) { set.insert(str); } // generating all combinations of binary strings of length N vector combinations; generateCombinations(0, N, "", combinations); // Traverse all the combinations and check if it is present in the set or not for (string str : combinations) { // If the combination is not present in the set, print it if (set.find(str) == set.end()) { cout arr = {"111", "001", "100", "110"}; printMissingCombinations(arr, N); return 0;}
登录后复制
输出
000010011101
登录后复制
时间复杂度 – O(N*2N)
空间复杂度 – O(2N)，因为我们将所有组合存储在数组中。
这两种方法使用相同的逻辑来解决问题。第一种方法使用迭代技术来找到长度为N的二进制字符串的所有组合，比第二种方法中使用的递归技术更快。此外，第二种方法消耗的空间比第一种方法多。
以上就是找到给定大小的二进制字符串数组中不存在的任意排列的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2587087.html
