找出不同的二进制字符串 图解题解
这道题到底在问什么
- 输入
- nums=["01","10"]
- 输出
- "11"(或 "00",任意一个不在数组里的即可)
- 输入
- nums=["00","01"]
- 输出
- "10"(或 "11")
- 输入
- nums=["1"]
- 输出
- "0"(把唯一一位翻过来)
先想最直接的笨办法
对第 i 行,答案在第 i 位上和它不同(行号对应的那一位被特意避开),所以 111000 与全部 6 个串都不同,它就是一个合法答案。只看了对角线 n 个格子,没枚举任何串。（动画第 24 步）
最优解：一步一步想明白
- 3记住这句:第 i 位 = nums[i][i] 取反。它保证答案与第 i 行至少差一位,对所有行都成立。下面每一帧都在套它。
- 4先把 6 个串排成 6×6 方阵。每行一个串,行号 = 串的序号。接下来只盯主对角线(左上到右下)上的 6 个格子。
- 5读第 0 行的对角格:nums[0][0] = 0。这是第 0 个串的第 0 个字符(紫色)。
当前对角字符 = 0 - 6把它翻转:0 → 1,写进答案第 0 位。这一格(蓝色)已定,答案与第 0 行至少在这一位不同。
答案第 0 位 = 0 取反 = 1 - 7读第 1 行的对角格:nums[1][1] = 0。这是第 1 个串的第 1 个字符(紫色)。
当前对角字符 = 0 - 8把它翻转:0 → 1,写进答案第 1 位。这一格(蓝色)已定,答案与第 1 行至少在这一位不同。
答案第 1 位 = 0 取反 = 1 - 9读第 2 行的对角格:nums[2][2] = 0。这是第 2 个串的第 2 个字符(紫色)。
当前对角字符 = 0 - 10把它翻转:0 → 1,写进答案第 2 位。这一格(蓝色)已定,答案与第 2 行至少在这一位不同。
答案第 2 位 = 0 取反 = 1 - 11读第 3 行的对角格:nums[3][3] = 1。这是第 3 个串的第 3 个字符(紫色)。
当前对角字符 = 1 - 12把它翻转:1 → 0,写进答案第 3 位。这一格(蓝色)已定,答案与第 3 行至少在这一位不同。
答案第 3 位 = 1 取反 = 0 - 13读第 4 行的对角格:nums[4][4] = 1。这是第 4 个串的第 4 个字符(紫色)。
当前对角字符 = 1 - 14把它翻转:1 → 0,写进答案第 4 位。这一格(蓝色)已定,答案与第 4 行至少在这一位不同。
答案第 4 位 = 1 取反 = 0 - 15读第 5 行的对角格:nums[5][5] = 1。这是第 5 个串的第 5 个字符(紫色)。
当前对角字符 = 1 - 16把它翻转:1 → 0,写进答案第 5 位。这一格(蓝色)已定,答案与第 5 行至少在这一位不同。
答案第 5 位 = 1 取反 = 0 - 17主对角线 6 格全部处理完(蓝色),取反拼起来 = 111000。下面逐行验证它确实与每一行都不同。
- 18对照第 0 行 011010:它的第 0 位是 0,而答案第 0 位是 1,这一位就不同(红格)。所以答案 ≠ 第 0 行。
差异位:0 vs 1 - 19对照第 1 行 101100:它的第 1 位是 0,而答案第 1 位是 1,这一位就不同(红格)。所以答案 ≠ 第 1 行。
差异位:0 vs 1 - 20对照第 2 行 110001:它的第 2 位是 0,而答案第 2 位是 1,这一位就不同(红格)。所以答案 ≠ 第 2 行。
差异位:0 vs 1 - 21对照第 3 行 001110:它的第 3 位是 1,而答案第 3 位是 0,这一位就不同(红格)。所以答案 ≠ 第 3 行。
差异位:1 vs 0 - 22对照第 4 行 010011:它的第 4 位是 1,而答案第 4 位是 0,这一位就不同(红格)。所以答案 ≠ 第 4 行。
差异位:1 vs 0 - 23对照第 5 行 100101:它的第 5 位是 1,而答案第 5 位是 0,这一位就不同(红格)。所以答案 ≠ 第 5 行。
差异位:1 vs 0 - 24对第 i 行,答案在第 i 位上和它不同(行号对应的那一位被特意避开),所以 111000 与全部 6 个串都不同,它就是一个合法答案。只看了对角线 n 个格子,没枚举任何串。
⚠️ 容易写错的地方
✗ 错：取错下标,用 nums[0][i] 之类
✓ 对：必须是 nums[i][i](第 i 行第 i 列)
只有第 i 位取 nums[i][i] 的反,才能保证答案与第 i 行不同
✗ 错：忘了翻转,直接拿对角字符
✓ 对：对角字符要取反
不翻转的话答案恰好可能等于某一行,失去「至少差一位」的保证
✗ 错：担心翻转后答案与其它行相同
✓ 对：不会:答案与第 k 行在第 k 位一定不同
对角线保证了答案对每一行都至少差一位,与「其它行」无关
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
return ''.join('1' if nums[i][i] == '0' else '0' for i in range(len(nums)))C++
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string findDifferentBinaryString(vector<string>& nums) {
string ans;
for (int i = 0; i < (int)nums.size(); ++i) ans.push_back(nums[i][i] == '0' ? '1' : '0');
return ans;
}
};Java
import java.util.*;
class Solution {
public String findDifferentBinaryString(String[] nums) {
StringBuilder ans = new StringBuilder();
for (int i = 0; i < nums.length; i++) ans.append(nums[i].charAt(i) == '0' ? '1' : '0');
return ans.toString();
}
}复杂度
时间
O(n)
只看对角线 n 个字符,每个翻转 O(1)
空间
O(1)
除答案串外只用常数变量(答案本身 O(n) 是必需输出)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 找出不同的二进制字符串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
能否把二进制串都转成整数,然后从 0 开始找第一个不在集合里的数?+
可以,把 nums 放进哈希集合,再从 0 数到 n,n+1 个候选里必有一个不在大小为 n 的集合里,找到即得。但要注意复杂度:把 n 个长度 n 的串逐字符转换或哈希、再把候选格式化成长度 n 的串,按字符计通常是 O(n²);而对角线法只读 n 个对角字符、无需哈希也无需转整数,是严格 O(n),常数更小、更优雅。
这道题和「缺失的第一个正数 / 寻找缺失数字」是一类思想吗?+
都是「在有限候选里构造或定位一个缺失值」。区别是本题用对角线构造(直接造出一个保证不同的),而缺失数字类常用原地标记或求和差去定位已有缺口。对角线法是构造型证明的经典范例。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 找出不同的二进制字符串 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。