确定是否超过一半的阵列重复更鲜明的阵列 [英] Determine if more than half of the array repeats in a distinct array

问题描述

我在看下面的<一个href="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"相对=nofollow>从Glassdoor 问题：

给定N个学分卡，确定其中一半以上属于同一人/所有者。所有你必须​​是信用卡号的数组，而像isSamePerson API调用（NUM1，NUM2）。

很清楚如何做到这一点的为O（n ^ 2），但有些评论者说，它可以在O（n）的时间来完成。它甚至有可能？我的意思是，如果我们有信用卡号码数组，其中重复一些数字，那么索赔是有道理的。但是，我们需要做一个API调用每个信用卡号码，看它的主人。

我是什么在这里失踪？

解决方案

则算法进行如下：

如果还有一大部分一项（在这里，一个人），然后如果你配对在一起是不相等的（以任意顺序）项目，该项目将被遗留下来的。

• 在开始一个空的候选时隙
• 对于每一个项目
  • 如果候选时隙是空的（数= 0），把它放在那里。
  • 否则如果它等于在槽的条，递增其计数。
  • 否则递减计数的插槽（弹出一个项目）。
• 如果没有什么留在候选时隙，也没有明确的多数。否则，
• 计数候选（二传）中出现的次数。
• 如果出现的次数超过50％，申报成为赢家，
• 否则不能形成多数意见。

请注意，如果该阈值是50％以下，这不能应用于（但它应该可以适应的33％，25％...的阈值由保持两个，三个......候选时隙和只弹出鲜明三，四......）。

这也apllies来的信用卡的情况下：所有你需要的就是比较两个要素（人）的平等（通过API调用），和一个计数器，它能够容纳的元素总数

时间复杂度： O（N）
空间复杂度： O（1） +输入
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屋！