确定数组的一半以上在不同的数组中重复 [英] Determine if more than half of the array repeats in a distinct array

问题描述

我正在查看以下问题：

$ b $给予N张信用卡，确定其中一半以上是否属于同一个人/拥有者。所有你有一个信用卡号码的数组，和一个api调用像isSamePerson（num1，num2）。

很明显如何在O（n ^ 2），但有些评论者表示可以在O（n）时间内完成。甚至有可能吗我的意思是，如果我们有一系列的信用卡号码，其中一些号码被重复，那么索赔是有道理的。但是，我们需要为每个信用卡号码拨打一个API来查看其所有者。

我在这里缺少什么？

解决方案

算法如下：

如果一个项目中有大多数（这里是一个人） ，那么如果将不相等的项目（按任何顺序）组合在一起，则该项目将被保留。

• 从空白开始候选插槽


• 对于每个项目
  
  
  
  • 如果候选插槽为空（count = 0），请放在那里。
  
  
  • 如果它等于插槽中的项目，则增加其计数。
  
  
  • 否则将该插槽的计数减去（弹出一个项目）。
  
  


• 如果候选插槽没有任何内容，则没有明确的多数。否则，


• 计算候选人的次数（第二次通过）。


• 如果发生次数超过50％，请声明一个赢家，


• 否则没有多数。

请注意，如果阈值低于50％（但是应该可以适应33％的阈值，25％...通过持有两个，三个...候选插槽，并且仅弹出一个明显的三重，四倍...） p>

这也是信用卡的情况：所有你需要的是比较两个元素（人物）相等（通过API调用）和一个能够

时间复杂度： O（N）

空间复杂度： O（1） + input

API调用：高达2N-1：每次通过一次，没有api调用第一个元素在第一次通过。

I was looking at the following question from Glassdoor:

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 credit card numbers, and an api call like isSamePerson(num1, num2).

It is clear how to do it in O(n^2) but some commenters said it can be done in O(n) time. Is it even possible? I mean, if we have an array of credit card numbers where some numbers are repeated, then the claim makes sense. However, we need to make an API call for each credit card number to see its owner.

What am I missing here?

解决方案

The algorithm goes as follows:

If there is a majority of one item (here, a person), then if you pair together items that are not equal (in any order), this item will be left over.

• Start with an empty candidate slot
• For every item
  • If the candidate slot is empty (count = 0), place it there.
  • Else if it is equal to the item in the slot, increment its count.
  • Else decrement the count for that slot(pop one item).
• If there is nothing left on the candidate slot, there is no clear majority. Otherwise,
• Count the number of occurences of the candidate (second pass).
• If the number of occurences is more than 50%, declare it a winner,
• Else there is no majority.

Note this cannot be applied if the threshold is below 50% (but it should be possible to adapt to a threshold of 33%, 25%... by holding two, three... candidate slots and popping only a distinct triple, quadruple...).

This also apllies to the case of the credit cards: All you need to is compare two elements (persons) for equality (via the API call), and a counter that is able to accomodate the total number of elements.

Time complexity: O(N)
Space complexity: O(1) + input
API calls: up to 2N-1: once in each pass, no api call for the first element in the first pass.

这篇关于确定数组的一半以上在不同的数组中重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！