9

Glassdoorからの次の質問を見ていました：

N枚のクレジットカードが与えられた場合、それらの半分以上が同じ人/所有者に属しているかどうかを判断します。あなたが持っているのはクレジットカード番号の配列とisSamePerson（num1、num2）のようなAPI呼び出しだけです。

O（n ^ 2）でそれを行う方法は明らかですが、一部のコメント提供者は、O（n）時間でそれを行うことができると述べました。それも可能ですか？つまり、いくつかの番号が繰り返されているクレジットカード番号の配列がある場合、その主張は理にかなっています。ただし、所有者を確認するには、クレジットカード番号ごとにAPI呼び出しを行う必要があります。

ここで何が欠けていますか？

4

5 に答える 5

17

アルゴリズムは次のようになります。

1つのアイテム（ここでは人）の過半数が存在する場合、等しくないアイテム（任意の順序）をペアにすると、このアイテムは残ります。

  • 空の候補スロットから始めます
  • すべてのアイテムについて
    • 候補スロットが空の場合（カウント= 0）、そこに配置します。
    • それ以外の場合、それがスロット内のアイテムと等しい場合は、そのカウントを増やします。
    • それ以外の場合は、そのスロットのカウントをデクリメントします（1つのアイテムをポップします）。
  • 候補スロットに何も残っていない場合、明確な過半数はありません。さもないと、
  • 候補の発生数を数えます（2回目のパス）。
  • 発生数が50％を超える場合は、勝者と宣言し、
  • それ以外の場合、過半数はありません。

しきい値が50％未満の場合、これは適用できないことに注意してください（ただし、2、3 ...の候補スロットを保持し、別個のトリプル、クワッドのみをポップすることで、33％、25％...のしきい値に適応できるはずです。 ...）。

これはクレジットカードの場合にも当てはまります。必要なのは、2つの要素（人）が等しいかどうか（API呼び出しを介して）と、要素の総数を収容できるカウンターを比較することだけです。

時間計算量：O(N)
スペース計算量：O(1)+入力
API呼び出し：最大2N-1：各パスに1回、最初のパスの最初の要素に対するAPI呼び出しはありません。

于 2013-02-07T21:31:33.197 に答える
3

x1、x2、...、xnをクレジットカード番号とします。

それらの半分以上が同じ人物に属しているため、2つの隣接する番号を考慮すると、少なくとも1つのペアが同じ人物に属していることに注意してください。

すべてのペア（x​​1、x2）、（x3、x4）....を検討し、両方の要素が同じ人物に属するペアのサブセットを検討すると、同一人物ペアの過半数は過半数を持つ人物に属します。そもそもカードの。したがって、すべての同一人物ペアについてはカード番号の1つを保持し、非同一人物ペアについては両方を破棄します。これを再帰的に実行し、最後に残っている同じ人物のペアを返します。

最大n個の比較を実行する必要があります。

注：nが奇数の場合は、対になっていない数を保持します。

これが機能する理由：nが偶数で、人物Aがn / 2+1枚のカードを所有している場合を考えてみます。最悪の場合、両方のカードがAによって所有されているペアが1つだけあります。その場合、他のペアは同じ人によって所有されていません（他のペアにはAの1枚のカードと他の人のカードが含まれます）。

ここで、一致するBのペア（A以外の人）を1つ作成するには、Bのペアも1つ作成する必要があります。したがって、すべてのインスタンスで、一致するペアの大部分はAによって所有されます。

于 2013-02-07T21:34:57.307 に答える
2

コメントする評判がありません。Jan Dvorakが語った方法は、Mooreの投票アルゴリズム（ストリームカウントアルゴリズム）として知られています。これがコードです。

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-MooreMajorityVoteアルゴリズムを使用します。私は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

ワンパスで完了：

  • 配列の2番目のインデックスから開始します。最初はi=1とします。
  • 最初はcount=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配列カウントの最後に>1の場合、1人の人物に属するカードの半分以上が存在します
  • それ以外の場合、50％を超える明確な過半数はありません。

これが理解でき、コードを書くのが簡単になることを願っています。

時間計算量-O（N）
API呼び出しの数= N-1
空間計算量-O（1）

于 2013-02-08T07:08:24.123 に答える