9

我正在查看Glassdoor 的以下问题：

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

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

我在这里想念什么？

4

5 回答 5

17

算法如下：

如果一个项目（这里是一个人）占多数，那么如果你将不相等的项目配对（以任何顺序），这个项目将被留下。

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

请注意，如果阈值低于 50%，则不能应用此方法（但应该可以通过保持两个、三个...候选插槽并仅弹出一个不同的三重、四重来适应 33%、25% 的阈值... ...）。

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

时间复杂度：O(N)
空间复杂度：O(1)+输入
API调用：最多2N-1：每遍一次，第一遍第一个元素没有API调用。

于 2013-02-07T21:31:33.197 回答
3

令 x1,x2,...,xn 为信用卡号。

请注意，由于其中一半以上属于同一个人，因此如果考虑两个相邻的数字，则至少其中一对将属于同一个人。

如果考虑所有对 (x1,x2), (x3,x4)....，并考虑两个元素都属于同一个人的对子集，则大多数同一人对属于拥有多数的人卡在第一位。因此，对于每个相同的人对，保留一个卡号，对于非同一个人对，丢弃两者。递归执行此操作并返回最后剩余的同一人对。

您最多需要执行 n 次比较。

注意：如果 n 是奇数，则保留未配对的数字。

为什么会这样：考虑 n 是偶数并且人 A 拥有 n/2 + 1 张牌的情况。在最坏的情况下，您恰好有一对，其中两张牌都归 A 所有。在这种情况下，其他对都不属于同一个人（其他对包含 A 的一张牌和其他人的牌）。

现在，要创建一对匹配的 B（非 A 人），您还必须创建一对 B。因此，在每个实例中，大多数匹配对都归 A 所有。

于 2013-02-07T21:34:57.307 回答
2

我没有评论的声誉。Jan Dvorak 所讲述的方法被称为摩尔投票算法（流计数算法）。这是代码。

int majorityElement(int* nums, int numsSize) {
int count =0, i, majorityElement;
/*Moore's voting algorithm Order(n), Auxiliary space: Order(1)*/
/*step:1-To get candidate for the majority element*/
for(i=0; i < numsSize; i++)
{
    if(count==0)
        majorityElement = nums[i];
    if(nums[i]==majorityElement)
        count++;
    else
        count--;
}
/*Step:2- To check whether this candidate occurs max no. of times */
count =0;
for(i=0; i<numsSize; i++)
{
    if(nums[i]==majorityElement)
        count ++;
}
if(count>numsSize/2) /*It can only be applied for majority check */
    return majorityElement; 
return -1;}
于 2016-10-10T21:39:22.033 回答
0

问题是找出数组中的多数元素。我将使用 Boyer-Moore 多数投票算法。我正在使用 HashMap 执行此操作。

public class majorityElement1 {
public static void main(String[] args) {
    int a[] = {2,2,2,2,5,5,2,3,3,3,3,3,3,33,3};
    fix(a);

}

public static void fix(int[] a ) {
 Map<Integer,Integer> map = new HashMap<>();

 for(int i = 0 ; i<a.length ; i++) {
     int r  = a[i];
     if(!map.containsKey(r)) {
         map.put(r, 1);
     }else {

         if(map.get(r) +1 >= a.length/2) {
             System.out.println("majority element => "+ r);
             return ;
             }else {
                 map.put(r,map.get(r) +1);
             }

     }//else1
 }//for
    }
}

输出为 3。

于 2018-03-23T09:11:27.583 回答
-1

一次性完成：

  • 从数组的第二个索引开始，最初说 i=1。
  • 最初计数=1。
  • 调用 isSamePerson(a[i],a[i-1]) 其中数组 a[] 包含信用卡号。
  • 如果返回值为正，则执行 count++ 和 i++
  • 否则，如果返回值为 0 并且 count==1 ，则 i++
  • 否则，如果返回值为 0 且 count>1 ，则执行 count-- 和 i++
  • 如果 i!=(n-1) ，转到第 3 步，其中 n 是牌的数量。
  • else 如果在数组的末尾 count>1 ，则有超过一半的卡片属于一个人
  • 否则，没有超过 50% 的明确多数。

我希望这是可以理解的，并且编写代码将是一件容易的事情。

时间复杂度 - O(N)
API 调用次数 = N-1
空间复杂度 - O(1)

于 2013-02-08T07:08:24.123 回答