面试官说:“给你一个整数数组,去一下重。”可以先写下 [3, 1, 3, 2, 1],问:“您想要的是每个数留一个,得到 [3, 1, 2],还是只留下从头到尾出现一次的数,得到 [2]?”两个答案都说得通,选哪一个会改变你接下来写的每一行。
下面用一场假设面试演示三次确认。每个问题都做一件事:让面试官的回答决定你下一步怎么写。微软在自己的技术面试指南里也建议,遇到歧义先提问、说明方案,再动手实现,写完后测试边界情况。本文的对话是一道练习题。微软技术面试指南
第一次确认:重复的值,留一份还是整组删掉?
候选人:“这个例子里,3 和 1 各出现两次,2 只出现一次。结果里还要有 3 和 1 吗?”
面试官:“要。每个不同的整数最后都留一个。”
到这里你已经知道,遇见一个新值可以把它列为候选答案。假如对方回答“只要出现一次的”,读到第一个 3 时就不能决定留它:后面还会出现第二个 3。一个直接的做法是先计数,再收集计数为一的值。第一问值得花时间,正因为这两道题的实现不同。
为什么不拿 [1, 2, 3] 举例?没有重复,两种解释都返回同一个结果。构造样例时,让有争议的条件真的发生。这个小习惯也适用于别的题目:问区间端点算不算重合,就拿恰好在端点接上的两个区间来试。

第二次确认:答案的顺序算不算对错?
候选人:“这个输入的结果,我能交[1, 2, 3],还是必须保留第一次出现的顺序,返回[3, 1, 2]?”
面试官:“保留第一次出现的顺序。”
这句话决定了实现里谁管顺序。可以让集合记住“这个整数见过没有”,同时用列表按遍历顺序记录第一次出现的值。如果直接把输入转成集合,再把集合转回列表,就无法靠这个操作保证原顺序。Python 明确把集合定义为无序集合;即使某次打印的顺序碰巧符合预期,也不能据此承诺保序。Python 集合类型文档
现在也能解释为什么“先排序再去重”不适用于这条约定。样例里的 3 明明最先出现,排序会让 1 跑到它前面。现场只要展示这一组输入和两个输出,对方就能看到你取舍的理由。
第三次确认:交回什么,能动哪份数据?
候选人:“我准备返回一个新列表,保留原输入,另用一个集合记见过的数。空间上允许吗?”
面试官:“可以。空列表就返回空列表。”
至此,可以把任务复述成一句可测试的话:“给定整数列表,返回按首次出现顺序去重的新列表,原列表保持原样。”题面已经把元素限定为整数,就没有必要再追问字符串的大小写。若题面一开始就写明要保序,同样可以跳过第二问。

写实现时可以口述三步:先准备一个空集合和一个空列表;按输入顺序读数,第一次见到某个数时,把它加入集合并追加到列表;最后返回列表。第一次读到 3 和 1 时都追加,第二个 3 跳过;接着追加 2,最后一个 1 跳过。结果就是 [3, 1, 2]。设共有 n 个整数、k 个不同的值,按整数哈希和查询平均为常数成本计算,这个实现平均耗时 O(n),集合和结果列表各占 O(k) 空间。
如果现场用 Python 3.7 或更高版本,也可以把同一项任务写成一个完整函数:def unique_in_order(values): return list(dict.fromkeys(values))。这里用字典的键记下每个不同的整数。字典保留首次插入顺序,后面再碰到已有的键不会改变位置,所以把键转成新列表即可。面试官若追问一行代码为什么成立,你已经有了前面的手算过程。Python 字典顺序说明
一组好样例怎样把问题问短
先把 [3,1,3,2,1] 摊开看。 如果题目只说“去重”,这一个样例就能把三种常见理解摆出来:按“每个值留一份,且保留第一次出现的顺序”,结果是 [3,1,2];按“只保留只出现一次的值”,结果是 [2];按“保留最后一次出现的值,并按末次下标排序”,先看 3 的末次下标是 2、2 的末次下标是 3、1 的末次下标是 4,所以结果是 [3,2,1]。同样一组数,三条解释三种答案,已经够说明题面没说完了。
但它还不是最短的。白板上更容易写的一组是 [1,2,1]。手算很快:如果按首现保留,第一次见到 1、2 就留下,结果是 [1,2];如果只要只出现一次的数,1 出现两次被删掉,只剩 [2];如果按末次下标排,1 的最后位置在 2,2 的最后位置在 1,所以顺序要反过来,结果是 [2,1]。三种输出两两不同,面试官几乎不用再猜。
为什么要追求“短而能分辨”?因为很多样例根本分不出来。比如 [1,2,3] 全都不同,三种解释都会给出 [1,2,3],看起来“都对”,其实什么也没确认;[2,2,2] 也一样,首现保留和末次排序都会变成 [2],还是分不开。这些输入适合检查其他边界,但单独用它们无法确定这里该选哪种定义。
还有一种常见误会,是把“去重”误听成“原地压缩并返回长度”。这时像 [1,1,3,3,4] 这样的有序输入就会出现有效前缀 [1,3,4],长度是 3;但这已经是另一道题了。题目一旦从“返回新列表”变成“原地写回”,你问的问题、写法和测试方式都要跟着变。
现场可以只递出这个短样例,先听对方给结果。如果回答是 [1,2],就接着确认“我按第一次出现的顺序各保留一份”;若回答是 [2],重点已经变成统计次数,暂时可以放下保序实现,继续问对方是否只需返回出现恰好一次的值。每一个问题都跟着刚刚收到的证据走。
如果你担心自己把顺序讲错,可以顺手把末次下标也说出来。比如在 [1,2,1] 里,1 的末次位置是 2,2 的末次位置是 1,所以“按末次下标排序”时 2 要排在前面。把“我怎么判断”的过程讲清楚,比只说一句“我会保序”更不容易出岔子。
再想想样例的选择成本。一个输入里同时塞进空值、负数、字符串和一堆重复,会让对方难以判断你到底在问哪个规则。先在题目明确给定的整数范围里,用三个元素分清定义,然后再单独拿空数组问返回类型。每次只改变一条条件,得到的答复才容易写进测试。
从集合和列表分别记什么,推到可以解释的正确性
先把“我到底在证明什么”说准。
如果题目要的是“每个不同的整数第一次出现时保留一次,并保持首次出现顺序”,那它和“只留下出现一次的数”不是一题。拿最短能区分三种规则的输入 [1,2,1] 试一下:首现结果是 [1,2],只出现一次是 [2],按末次下标则是 [2,1]。所以这道题的目标不是“去重”两个字,而是“首现保序去重”。
接下来,证明的骨架其实很简单:每轮都维护一个不变式。
设 seen 是已见集合,result 是结果列表。处理完输入前缀以后,要始终满足两件事:第一,seen 里包含这个前缀中出现过的所有不同整数;第二,result 按这些整数第一次出现的先后顺序排列。先看具体例子 [3,1,3,2,1]。开始时前缀为空,seen 也是空集合,result 也是空列表,显然成立。
读到第一个 3 时,3 不在 seen,于是把它加入 seen,result 变成 [3]。这时前缀是 [3],两个条件都成立。读到 1 时,同样是第一次见到它,于是 seen={3,1},result=[3,1]。第三个数还是 3,它已经在 seen 中,所以什么都不做;这一步很关键,因为“第一次出现才进结果”已经被集合替我们确认过了。再读到 2,它是新值,于是加入后得到 seen={3,1,2},result=[3,1,2]。最后读到 1,仍然已经见过,跳过即可。整轮结束后,result 恰好就是首现保序答案。
为什么这就算证明,而不只是“这个例子跑通了”?因为每一步都只有两种情况。若当前数 x 已在 seen 中,它在当前前缀里已经有过第一次出现,按定义不该再进 result;若不在 seen 中,它就是当前前缀第一次见到的这个值,按定义必须追加到 result 末尾,同时加入 seen 方便后面识别重复。这样“前缀处理完后的性质”在每轮前后都被保持住,最后自然得到整段输入的正确答案。空数组也直接成立:前缀一开始就是空,不进入循环,返回空列表即可。
如果你想把这个推理再说得硬一点,可以把它写成归纳:长度为 0 时成立;假设前 i 个数处理后不变式成立,处理第 i+1 个数时,只要根据它是否在 seen 中分别执行“跳过”或“加入”,不变式就继续成立。这里真正依赖的是整数的哈希查找在平均意义下可以看作常数时间,seen 的插入和查询平均都是 O(1)。
也正因为如此,这种写法平均时间是 O(n),其中 n 是输入长度;seen 和 result 都只保存不同的值,空间是 O(k),k 是不同整数的个数。这个平均结论有前提:我们把整数的哈希和相等比较都视作常数代价,并接受哈希表的常见平均行为。若不满足这些前提,就不能把 O(1) 说得太满,但面试里的标准讨论通常就是这套假设。
反过来,如果只用一个列表 result 自己判重,算法依然可能正确,却会慢得多。假设输入里全都不重复,长度是 n。第 1 个元素不需要比较;第 2 个要和前 1 个比;第 3 个要和前 2 个比……第 n 个要和前 n-1 个比。总比较次数是 1+2+...+(n-1)=n(n-1)/2,这不是模糊的“大概很多”,而是确切的平方级开销。比如 n=4 时,正好是 6 次比较。
你可以自己再做一遍小练习:把输入换成 [1,2,1],按“读到什么、seen 里有什么、result 现在是什么”三列在脑子里过一遍。你会发现,第三个 1 之所以不进结果,不是因为它“看起来像重复”,而是因为集合已经替你记录了“它早就出现过”。这就是这道题最值得讲清楚的地方:不是背一个模板,而是能解释为什么每一轮都不会把答案写歪。
面试官改了一个条件,要能换解法
假设现在给出的输入已经排好序,要求在原列表前部写下去重结果,并返回有效长度。这时相同值连续出现,只要记住已经写了多少个值,再依次把不同的值往前填。对 [1, 1, 3, 3, 4],返回长度应为 3,前 3 个元素是 [1, 3, 4]。题目只检查这段有效前缀,尾部留下什么没有关系。
反过来,如果只把输入换回无序的 [3, 1, 3],上面这种只看相邻值的做法就会漏掉第二个 3。面试时讲清“我依赖输入有序”比只背“双指针,常数空间”更有用。遇到“输入能改吗”这样的追问,也能指出它会改变返回值和测试方式。

当条件改成有序且原地,怎样在白板上改方案
题目一旦改成“输入已经有序,而且要原地写回前缀”,解法就从“收集见过的值”变成“维护一个有效前缀”。 对白板来说,最清楚的画法不是先写代码,而是先画两个指针:read 从左到右扫描,write 指向“下一个可以写入的位置”。read 负责找新值,write 负责标记前缀长度。对 [1, 1, 3, 3, 4],可以把第一个 1 视为已经留在前缀里,于是 write=1,read=1 从第二个元素开始看。
先读索引 1 上的第二个 1,与有效前缀末尾的 1 相同,跳过。再读索引 2 上的 3,把它写到索引 1,随后将 write 加一。此时完整数组是 [1,3,3,3,4],有效前缀只有 [1,3];索引 3 和 4 目前还没有读,必须保留供后续读取。接着读索引 3 上的第二个 3,跳过;最后把 4 写入索引 2。完整数组变成 [1,3,4,3,4],返回的有效长度为 3。现在才可以忽略末尾那两个元素。
这个过程中最重要的结论有两个:一是比较对象永远是“当前有效前缀的最后一个值”,不是原数组里某个固定位置;二是尾部不用验。因为题目只检查返回的长度和前 write 个元素,后面残留着旧值没关系。你在白板上甚至可以直接把最后两个位置圈起来,告诉面试官:“这里不清理,因为它已经不属于有效前缀了。”这样讲,比泛泛地说“原地覆盖”更容易让对方确认你真的懂这个约束。
用最小输入检查初始化。 假设有人用 write=0 开始,处理头一个元素时就比较 nums[read] 和 nums[write-1]。在 Python 里下标 -1 是最后一个元素。拿 [7] 试一下,这两个位置恰好表示同一个 7,算法跳过它,错误返回 0。更稳的写法是先单独处理空数组;非空时第一个数天然可以保留,初始化 write=1,从第二个数开始读。写下这个约定后,也就能解释为什么每次用 write-1 都指向有效数据。
还有一种容易被忽略的误判,是把这套方法拿去处理无序数组。比如 [1, 2, 1],你会发现“和前一个不同就写入”的规则根本抓不住最后那个 1,因为相同值没有连续出现。也正因为如此,这道题里“有序”不是装饰条件,而是算法成立的前提;一旦条件没了,就不能继续说“只要双指针原地扫描就行”。这个反例也顺手提醒你,面试时别把“排序后再去重”混成同一道题——排序一旦加入,题目和复杂度都变了。
按这个约定分析空间复杂度时,只能算你真正额外用了什么。这里除了 read、write 和一个临时比较变量,没有再开新集合或新列表,所以额外空间是 O(1)。但这不是“任意排序都常数空间”,因为这题根本没让你排序;如果你为了偷懒先排序,那就已经换题了,不能再把这段分析原封不动搬过去。时间上,read 只走一遍数组,每个元素最多比较一次并在必要时写一次,因此是线性扫描。
让同学报出三个中间状态:跳过第二个 1 之后 write 等于多少;首次读到 3 时,覆盖的是哪个下标;读到 4 前,前缀末尾是谁。答案依次是 1、索引 1、数值 3。如果只给出最终的长度 3,几个更新次序不同的伪实现看起来可能都说得通。能说清每步读了哪里、写了哪里,才方便定位某次覆盖为何丢了数据。
同一个数的最后一条记录才算数时
先把题意掰开:身份是 id,内容是最后一次修订,输出顺序另算。 这次不是“整数去重”,而是“记录去重”:输入按到达先后排列,每条记录都有 id 和 rev 之类的修订字段。比如 A1 表示 id=A, rev=1,A2 表示同一 id 的第二次修订。面试官如果只说“去重”,你先问一句:“同一个 id 的旧记录要不要被后来的修订覆盖?输出里是保留最后一条,还是只保留出现一次的?”这句话把“身份”和“覆盖”拆开了,不容易把 set 当成答案容器。
用一条变更记录来区分它们。按到达顺序,样本是 A1、B1、A2。最后应该留下 A2 而非 A1,这点双方已经同意。争议在于交付文件的第一行:按账号首次出现顺序排,A 先到,所以输出 [A2,B1];按保留下来的记录实际到达顺序排,B1 早于 A2,所以输出 [B1,A2]。两份文件都包含最新版本,读者浏览它们时却会看到不同的顺序。
只用一个集合记下 A 和 B,能回答“出现过哪些账号”,却没有记录每个账号最后到达的内容。如果改成按整条记录判相等,A1 和 A2 又可能都留下。可以把两个问题分别写在白板上:用哪个字段当键,以及同一个键再次出现时应当覆盖哪份值。随后再决定最后按照什么顺序遍历这些键。
如果题目要的是“保留最后内容,但按首次出现排”,可以先扫一遍,把每个 id 的最后一条记录记到字典里,再额外记住 id 的首次出现顺序。对 A1,B1,A2,第一次见到 A 和 B 时把它们记入顺序表,后来 A2 来了就覆盖字典里 A 的值。扫完以后,按首次出现的顺序取字典里的最新记录,得到 [A2,B1]。这个做法的关键不是“最后一次覆盖了谁”,而是“最后内容要跟着首次出现的排序走”。
如果题目改成“按最后出现下标排”,就换成另一种合法答案:还是先记录每个 id 的最后一条记录,再把这些记录按最后下标从小到大排。对 A1,B1,A2,B 的最后位置在前,A 在后,所以输出 [B1,A2]。这两种算法都对,但它们回答的是不同问题。面试时如果不问清,就会把“保留最后内容”误听成“保留最后顺序”,结果写到一半才发现方向错了。
你可以直接这样问,既不绕也不硬:“我理解这里有两个独立条件:第一,按 id 保留最后一条修订;第二,输出顺序是按首次出现,还是按最后出现下标?如果您没指定,我先按首次出现来写。”这句话比泛泛地问“顺序怎么算”更有用,因为它把两个可变点都钉住了。
有个更接近工作场景的追问:如果传来的修订号依次是 2、1,还保留后到的那条吗?这时要问业务上的“最后”指到达时间,还是指最大的修订号。本题已经给定按到达先后处理,所以后到的修订 1 会覆盖先到的修订 2。如果题目改成取最大修订号,则需要先比版本再决定是否覆盖;相同版本又出现时,也要约定是否按新记录处理。
如果按末次下标排序,记下最后位置的扫描平均为 O(n),对 k 个不同账号按下标排序还需要 O(k log k)。当输入可以倒序访问,也有一种平均 O(n) 的走法:从后往前扫描,第一次遇到某个账号就留下它,再把收集到的列表反转。这次反转的作用,是把“最晚的先捡到”恢复为“保留记录按原输入先后排列”。两种方法各自依赖什么,要在声称复杂度之前交代清楚。
可以用这两个方案解释一次取舍:输入若是只能向前读的数据流,倒序方案不能直接使用。可以保存每个账号的最新内容和最后位置,流结束后再排这 k 个条目;如果题目还要求每来一条就立即输出最终答案,需要先讨论输出是否允许撤回,否则你在第一条 A 到达时就无法知道后面会不会出现 A2。
交卷前,用四组数据检查约定
测试输入 | 期望的新列表 | 它能发现什么 |
|---|---|---|
[] | [] | 是否忘了处理空输入 |
[7, 7, 7] | [7] | 是否误把重复出现的值全部删除 |
[3, 1, 3, 2, 1] | [3, 1, 2] | 是否漏掉隔开出现的重复,或者擅自排序 |
[4, 2] | [4, 2] | 全部不同的时候,顺序是否仍然正确 |
最后一行还有个容易忽略的检查:题目要求返回新列表,直接返回输入对象,在打印结果时看不出差别。保存一份输入快照,调用后检查原输入内容不变、返回对象与输入对象不同,才把这条承诺也测到了。
自己练习时,可以把开场的一句话录下来听听。能给出一个让两种解释产生不同结果的样例,确认什么会影响代码,然后自然地说出“我现在准备这样写”,就可以开始了。
给自己的解法挑错:怎样设计能区分错误实现的测试
先挑具体错误,再挑能暴露它的输入。只准备一个“标准示例”容易让偶然正确的实现混过去。同样是判重失败,有的实现只看相邻元素,有的实现误删整组,有的实现内容看起来对却改变了顺序。下面这组练习的目标,是让每个失败都能提示下一步该看哪段逻辑。
先看“只处理相邻重复”的错法。拿 [1,2,1] 就够了:相邻位置没有相等元素,它会原样返回 [1,2,1]。如果你断言的是“结果应等于 [1,2],并且长度变成 2”,它立刻过不了;如果你只断言“没有连续重复”,它反而可能蒙混过关。这个样例抓得住“只看邻居”,却抓不住“排序后再去重”,因为把 [1,2,1] 排序后也会变成 [1,2],看上去和首现答案一样。
检查擅自排序,最小反例可以只用 [3,1]:元素根本不重复,正确输出仍是 [3,1],排序后则成了 [1,3]。如果想在一轮测试中顺带检查重复项,可换成 [3,1,3]。两组数据问的都是“第一个出现的值还在第一位吗”,但前一组把其他干扰因素都拿掉了。只断言输出的元素种类或长度,这类错法都可能通过。
第三种常见错法,是把“计数恰为一”的值当成去重结果。[1,2,1] 会马上揭穿它:正确答案还有一个 1,而这种实现只会留下 [2]。这时要断言的是“每个不同的值都应保留一份,而不是把重复值整个删掉”。如果你想更直观一点,[1,1,3,3,4] 也能看出来:正确的首现结果应是 [1,3,4],不是只剩最后那个单独的 4。这个样例抓得住“误删重复值”,却不负责检查顺序细节。
检查“返回新列表”时,可以用 [4,2]。正确实现与直接返回输入的实现都可能打印 [4,2],所以除了比内容,还要断言返回对象与输入对象不是同一个。为了检查函数执行时是否偷偷改过输入,调用前先保存一份内容快照,调用后与快照对比。再向返回的列表追加一个值,输入也不应多出那个值。空列表同样能检验身份,但含有两个值的例子更便于在白板上展示操作结果。
让检查同时照顾覆盖和顺序。 先查输入输出的不同值集合是否相同,避免遗漏,再查输出长度是否正好等于不同值的个数,避免重复。对输出中每个值求它在输入里的首次下标,这些下标必须严格递增。仅要求“是输入的一个子序列”还不够:对 [1,2,1],错误输出 [2,1] 也确实是子序列,却违背了首次出现的顺序。
幂等性可以再补一项:把结果再次去重,内容应当不变。但恒返回空列表也满足这条性质,不能用它代替覆盖检查。练习时,把某个断言临时删掉,再寻找一个能通过剩余断言的错误实现。删掉顺序检查,排序去重就可能混过去;删掉覆盖检查,只留下部分输入也可能蒙混过关。你既能写正例,也能解释每条测试究竟承担什么职责。
面试官让你自己定,怎样把假设说完并继续写
换一道独立练习:面试官给了两段时间,只说“判断是否相交,其他你自己定”。可以先问端点相碰算不算,比如 [1,3] 和 [3,5]。完全没接触和明显交叠的例子,都不会逼你决定这个条件。接着说清输入是两段有效区间,各自起点不晚于终点。对这样两段时间,先后输入的次序并不影响相交判定。
候选人可以说:“我先按闭区间算,端点 3 也算交点;如果业务是前一个预约结束后可以马上开始下一个,我会改用左闭右开。接下来先按前一种写。”对方让你自行决定时,说出默认值,并给一个能让默认值失效的场景,就可以继续推进。此时只处理两段区间,并不需要先排序。
接着你可以把方案复述成一句话:“在闭区间前提下,两段区间是否重叠,只看它们的最大起点是否不大于最小终点。”写成判断就是 max(a1, a2) <= min(b1, b2)。这个式子一眼能检查:若改成 <,就会把 [1,3] 和 [3,5] 误判为不重叠,反例马上就能抓出来。面试里最好别只说“我觉得应该这样”,而是把能推翻错误理解的样例一起摆上来。
现在改变输入规模:假设有一份包含多段时间的预约清单,要找出是否有任意两段冲突。这个时候再问“清单是否按开始时间排好、能不能改原顺序”才有意义。若输入无序并允许另开列表,可以先按开始时间排序副本再扫描。如果不允许改输入,还严格限制额外空间,逐对比较也是一种明确可行的取舍:它多花时间,却用不到一个待排序的副本。
你可以自己先答这个练习:同学 9:00 到 10:00 练琴,你 10:00 到 11:00 上课,这两段算冲突吗?先别看下面。若按闭区间理解,答案是“算”,因为 10:00 是共同端点;若有人把时间段当成左闭右开 [9:00,10:00) 和 [10:00,11:00),那就“不算”。所以真正该先问的,不是“怎么做”,而是“端点怎么算”。
换成先给晚场、再给早场,例如 [5,6] 和 [1,2]。仅凭“第一段的结束时间大于第二段的开始时间”,会把两个相隔很远的闭区间错判成重叠。套用前面的公式,最大起点为 5,最小终点为 2,5 不小于等于 2,所以没有交点。这道反例把输入顺序颠倒了,专门检查实现是否暗中依赖“先给的那段一定更早”。
对于已经按开始时间排序的单份清单,可以扫一遍,记下已处理区间的最大终点。若当前起点不大于这个最大终点,两段闭区间就有冲突;否则把当前终点纳入记录并继续。约定成非空左闭右开区间时,把比较改为严格小于。这里存一个终点即可,不用复制整份清单。判断单个清单内部是否有冲突,与找两份有序清单之间的交集是不同任务,别把后者的双指针口诀原样套进来。
最后再把这道新练习还给同学。你先只说“判断两个预约是否冲突”,让他提问;第二轮补一句“要查整个日历”,看他在哪一刻开始询问顺序和额外空间。用这个变化检查自己的习惯:会随着答案调整实现的条件值得先问,眼前根本用不到的信息则可以暂时放下。







