algorithm - 确定是否有超过一半的数组在不同的数组中重复

Question

我正在查看以下 question from Glassdoor :

给定 N 张信用卡，确定其中是否超过一半属于同一个人/所有者。您所拥有的只是一组信用卡号和一个 api 调用，例如 isSamePerson(num1, num2)。

很清楚如何在 O(n^2) 内完成，但一些评论者表示可以在 O(n) 时间内完成。有可能吗？我的意思是，如果我们有一组信用卡号码，其中一些号码重复，那么这个说法是有道理的。但是，我们需要为每个信用卡号调用 API 以查看其所有者。

我在这里错过了什么？

Answer 1

算法如下:

如果一个项目(这里是一个人)占多数，那么如果您将不相等的项目配对(以任何顺序)，则该项目将被剩下。

• 从一个空的候选位置开始
• 对于每个项目
  • 如果候选位置为空(计数 = 0)，则将其放在那里。
  • 否则，如果它等于插槽中的项目，则增加其计数。
  • 否则减少该插槽的计数(弹出一项)。
• 如果候选位置上没有任何剩余，则没有明显的多数。否则，
• 计算候选人出现的次数(第二遍)。
• 如果出现次数超过 50%，则宣布获胜，
• 否则没有多数。

请注意，如果阈值低于 50%，则无法应用此方法(但应该可以适应 33%、25%...的阈值，方法是保持两个、三个...候选位置并仅弹出一个不同的三倍，四倍...)。

这也适用于信用卡的情况:您只需比较两个元素(人)是否相等(通过 API 调用)，以及一个能够容纳元素总数的计数器。

时间复杂度:O(N)
空间复杂度:O(1) + 输入
API调用:最多2N-1次:每pass一次，第一pass第一个元素不调用api。