数组中重复次数最多的数

Question

我被问到一个面试问题，要求我返回数组中重复次数最多的数字，例如，{1,1,2,3,4}返回1。

我首先在hashtable中提出了一种方法，它要求空间复杂度O(n)。然后我说先对数组排序，然后遍历它，然后我们就可以找到数字了。

有什么优化吗？

谢了。

Answer 1

面试官并不总是在寻找解决方案本身。有时他们会想知道你做其他事情的能力。您应该询问这些数据是否有任何限制，例如：

• 是否已排序？
• 值是否限制在某个范围内？

这建立了你思考问题的能力，而不是一味地吐出课本上读过的东西。例如，如果它已经排序了，您可以在O(n)个时间，O(1)个空间中进行排序，只需查找具有最大大小的运行。

• 如果有两个计数相同的数字，他们想要什么样的行为？
• 如果他们对你提供的解决方案不满意，试着了解他们在想什么。他们认为可以在O（log N）或O(1)中完成吗？面试从来都不是单行道。

还有很多其他的“解决方案”，比如将整个内容存储到一个类中，这样您就可以执行其他优化（比如缓存信息，或者使用不同的数据结构来加快操作）。和你的面试官讨论这些会让他们有机会看到你的行动。

顺便说一句，我告诉我的孩子们在他们的学校作业中要经常展示锻炼。如果他们只是扑通一声把答案写下来，结果是错的，他们什么也得不到。然而，如果他们展示了他们的工作，并得到了错误的答案，老师至少可以看到他们的想法是正确的（他们可能只是在过程中犯了一个小错误）。

这里完全一样。如果你简单地说“hashtable”，而面试官有不同的想法，这将是一个相当短的面试问题。

底线是，当面试官问你一个问题时，不要总是假设它像你最初想的那样简单。除了技术知识，他们可能会看到你如何解决问题，如何处理小林丸式的问题，如何在团队中工作，如何对待难缠的客户，你是否是一个秘密的精神病患者，以及其他无尽的可能性。