数组问题和二分法问题一样，是互联网公司技术岗面试中很常见的考点。我在上一篇文章中分享了二分法问题的解答思路，指路我的文章 《IT大厂面试经验分享 —— 二分法》。

给第一次看文章的小伙伴介绍下自己～ 我在ACM/ICPC比赛中拿过亚洲区金牌，现在是TMD（今日头条，美团，滴滴）中一家的资深工程师，面试过上百位候选人。

话不多说，今天我来分享一道数组题目和解答思路：

“如何高效地在一个有大量重复数字的数组里，找到那个唯一落单的数字？”

举个栗子：. 一个数组里面大部分数出现的次数都是偶数次，有且仅有一个数只出现一次，能否用 O(1) 的时间复杂度将这个落单的数找出来。如 [1,2,3,1,2] 里找出 3 是落单的数。

关于这个问题，其实是有不少技巧性的，不同的算法模型，效率相差很多，当面试时遇到这类的问题，如何在面试官心中拿到高分。一起来看看吧。

60分的答案
利用排序算法将相同的数靠在一起，落单的数就是那个既和左边不一样，也和右边不一样的数。
时间复杂度：排序算法复杂度

面试官 OS：没有利用“偶数次”这个条件，速度比最优算法慢上不少。

80分的答案
了解位运算，能发现异或操作与偶数次的联系，将所有数都异或一遍就能得到落单的数
时间复杂度：O(n)

面试官 OS：思路敏捷，可造之材，不过考验才刚刚开始，现在题目稍微改一下，有两个数落单了，能把它们都找出来吗？

面试官加大题目的难度，既是挑战，同时也是巨大的机遇！

90分以上的答案
了解异或操作的本质，利用所有数的异或结果，得知这两个落单的数不同位是哪些，按某一个不同位，将数组分成两份，将问题退化至两个找“唯一落单”的问题，得到答案。
有点小复杂？下面举个栗子说明:
例：假设落单的数是 2 和 3， 2 的二进制 10， 3 的二进制 11， 异或的结果是 01，就可以知道两个落单的数第一位不一样，然后将数组按第一位是 0， 第一位是 1 分成两个数组，2 和 3 自然就分开了，再分别异或两个数组的所有数，就能得到 2 和 3。

面试官OS：人才，立刻入职，明天就来加班。

今天分享到这里，喜欢我的文章的小伙伴关注我吧～ 我在牛客每周分享一道面试题，助你斩获大厂Offer!

作者：私坊茶话
链接：https://www.nowcoder.com/discuss/441858?channel=0&source_id=home_feed
来源：牛客网

看似最简单的问题，不同的回答却高下立判。现在总结出来的高分答案，都是当年求职一步一个坑摸索出来的血泪之谈。

所以，我们成立了【私坊话IT】—— 专注于IT行业高端岗位的求职培训品牌，真心地，希望能在你的圆梦路上，助你一臂之力。

我们团队成员都是来自

国内外科技大厂的资深工程师

毕业于全球Top30、国内Top5高校

当年均OFFER拿到手软

混迹于科技圈多年

现均为各领域专家、团队负责人

掌握着专项领域最前沿技术

积累了丰富的工作与求职经验

能给予你最透彻的解析