记 dotamax 面试第一题

前言 正文 思路 存在一个数字 存在两个数字 总结

前言

今天接到了一个面试，面试官鑫哥声音很好听，人也很好，是我目前见到的所有面试官中最好的一位啦。

可能还是知识面比较窄，第一个问题就把我给问倒了。一是太紧张，二是本身能力可能也没那么强，所以第一题没能想出来。面试完后，心里还是坠着一个石头似得，就一个想法，把这个问题搞明白，实现了。

于是下午，着手实现了一下，在此做个笔记，希望对后来人能有所帮助。

正文

这道题的内容是这样的：

给一个数组，数组中只有一个元素出现了仅仅一次，其他元素都是出现了两次。请用空间复杂度为O(1)和时间复杂度为O(n)的算法找出这个数。

说实话，我第一反应就是：“尴尬，这下完蛋了”。肯定不是正规思路了。然后就想啊想啊，最后勇于向鑫哥承认，这道题我确实没有什么好的办法。