我正在看以下内容来自 Glassdoor 的问题 http://www.glassdoor.com/Interview/Given-N-credits-cards-determine-if-more-than-half-of-them-belong-to-the-same-person-owner-All-you-have-is-an-array-of-the-QTN_384804.htm:
给定 N 张信用卡，确定其中一半以上是否属于同一个人/所有者。您拥有的只是一个信用卡号数组和一个像 isSamePerson(num1, num2) 这样的 api 调用。
很清楚如何在 O(n^2) 时间内完成，但一些评论者说它可以在 O(n) 时间内完成。有可能吗？我的意思是，如果我们有一系列信用卡号，其中某些数字重复，那么该索赔就有意义。但是，我们需要对每个信用卡号进行 API 调用才能查看其所有者。
我在这里缺少什么？
算法如下：
如果一个项目（这里是一个人）占多数，那么如果您将不相等的项目（以任何顺序）配对在一起，则该项目将被剩下。
- 从空候选槽开始
- For every item
- 如果候选槽为空（计数 = 0），则将其放置在那里。
- 否则，如果它等于槽中的项目，则增加其计数。
- 否则减少该槽的计数（弹出一项）。
- 如果候选人空缺，则不存在明显多数。否则，
- 计算候选者出现的次数（第二遍）。
- 如果出现次数超过50%，则宣布获胜，
- 否则就没有多数。
请注意，如果阈值低于 50%，则不能应用此方法（但应该可以通过保留两个、三个……候选槽并仅弹出不同的三元组、四元组来适应 33%、25% 的阈值…… ...）。
这也适用于信用卡的情况：您所需要做的就是比较两个元素（人）是否相等（通过 API 调用），以及一个能够容纳元素总数的计数器。
时间复杂度：O(N)
空间复杂度：O(1) + input
API 调用：最多 2N-1：每遍一次，第一遍中的第一个元素没有 api 调用。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
