LeetCode 1980. 找出不同的二进制字符串题目描述给你一个二进制字符串数组nums包含n个互不相同的二进制字符串每个字符串长度均为n。请你找出并返回一个长度为n且没有出现在nums中的二进制字符串。如果存在多个答案只需返回任意一个即可。示例 1输入nums [01,10] 输出11 解释11 没有出现在 nums 中00 也是正确答案。示例 2输入nums [00,01] 输出10 或 11示例 3输入nums [111,011,001] 输出101 或其他不在列表中的二进制串提示n nums.length1 n 16nums[i].length nnums[i]为0或1nums中的所有字符串互不相同解题思路本题最直接的解法是枚举所有可能的长度为n的二进制串共2^n个检查哪些不在nums中。但由于n最大为 162^n可能高达 65536完全可行但这不是最优解。题目要求我们构造一个不在nums中的串而不是去查找。利用康托尔对角线法我们可以在O(n)时间内直接构造出一个满足条件的字符串。对角线构造法对于nums中的第i个字符串nums[i]取其第i个字符即对角线上的字符然后将其取反作为新串ans的第i位。即ans[i] (nums[i][i] 1) ? 0 : 1;这样构造出来的ans长度为n并且对于任意k ∈ [0, n-1]ans的第k位与nums[k]的第k位不同因此ans不可能等于任何一个nums[k]即ans一定不在nums中。正确性证明假设ans等于某个nums[j]那么ans的第j位就应该等于nums[j]的第j位。但根据构造规则ans的第j位恰好与nums[j]的第j位相反矛盾。故ans不可能出现在nums中。举例说明以nums [111,011,001]为例n3i0取nums[0][0] 1→ans[0] 0i1取nums[1][1] 1→ans[1] 0i2取nums[2][2] 1→ans[2] 0得到ans 000检查发现000确实不在原数组中。如果原数组是[01,10]i0nums[0][0] 0→ans[0] 1i1nums[1][1] 0→ans[1] 1得到ans 11符合要求。代码实现classSolution{public:stringfindDifferentBinaryString(vectorstringnums){string ans;intnnums.size();for(inti0;in;i){// 取对角线的字符并取反ans(nums[i][i]1)?0:1;}returnans;}};复杂度分析时间复杂度O(n)只需一次遍历每次常数时间操作。空间复杂度O(1)或O(n)若计入结果字符串则为O(n)否则为额外空间O(1)。总结本题利用经典的对角线论证法巧妙地构造出一定不在原数组中的二进制串避免了枚举或查找。思路简单代码简洁是解决此类“找出缺失串”问题的利器。注意此方法构造出的串可能不是唯一的答案但题目只要求返回任意一个即可因此完全符合题意。