确定是否有一半以上的数组在不同的数组中重复

Question

我正在看Glassdoor的以下问题:

给定N个信用卡,确定其中一半以上是否属于同一个人/所有者.你所拥有的只是一组信用卡号码,以及像isSamePerson(num1,num2)这样的api调用.

很明显如何在O(n ^ 2)中完成它,但一些评论者表示可以在O(n)时间内完成.它甚至可能吗？我的意思是,如果我们有一系列信用卡号码,其中一些数字被重复,那么这个说法是有道理的.但是,我们需要为每个信用卡号码进行API调用以查看其所有者.

我在这里错过了什么？

Answer 1

算法如下:

如果一个项目(这里是一个人)的大多数,那么如果你将不相等的项目(按任何顺序)组合在一起,这个项目将被遗留下来.

• 从空的候选插槽开始
• 对于每个项目
  • 如果候选槽是空的(count = 0),则将其放在那里.
  • 否则,如果它等于插槽中的项目,则增加其计数.
  • 否则减少该槽的计数(弹出一个项目).
• 如果候选插槽上没有任何东西,则没有明显的多数.除此以外,
• 计算候选人的出现次数(第二次通过).
• 如果出现次数超过50%,宣布为胜利者,
• 否则没有多数.

请注意,如果阈值低于50%,则无法应用此值(但应该可以通过保持两个,三个......候选插槽并仅弹出一个不同的三倍,四倍来适应阈值33%,25%...... ...).

这也apllies来的信用卡的情况:所有你需要的就是比较两个要素(人)的平等(通过API调用)和计数器,它能够容纳的元素总数.

时间复杂度:O(N)
空间复杂度:O(1)+输入
API调用:最多2N-1:每次传递一次,第一次传递中没有api调用第一个元素.