2

配列（ほとんどの場合に表示される数値）で過半数を見つけたい。私はソートされた配列を持っており、これらのサイクルを使用しています:

for(int k = 1;k < length;k++)
{
    if(arr[k-1] == arr[k])
    {
        count++;
        if(count > max)
        {
            max = count;
            maxnum = arr[k-1];
        }
    } else {
        count = 0;
    }
}

また

for(int h=0;h<length;h++)
{
    for(int l=1;l<length;l++)
    {
        if(arr[h] == arr[l])
        {
            count++;
            if(count > max)
            {
                max = count;
                maxnum = arr[h];
            }
        } else count = 0;
    }
}

それらは似ています。小さな配列でそれらを試してみると、すべて問題ないようです。しかし、N 個の要素 0<=N<=500000 を持つ長期配列では、各要素 K 0<=K<=10^9 は間違った答えを返します。これが間違いhttp://ideone.com/y2gvnXの解決策です。過半数を見つけるためのより良いアルゴリズムがあることは知っていますが、どこが間違っているのかを知る必要があります。

私は本当にそれを見つけることができません:(本当に助けていただければ幸いです!

4

4 に答える 4

1

まず、first algorithm配列がソートされているため、を使用する必要があります。2 番目のアルゴリズムは、配列を不必要に 2 回実行します。

今、あなたfirst algorithmはほぼ正しいですが、2つの問題があります: -

  • 最初の問題はcount = 0、else の部分で を設定していることです。むしろ、 に設定する必要があります1。すべての要素が少なくとも 1 回来るためです。
  • max第二に、毎回設定する必要はありませんif。ただ increment count、if-conditionが満たされるまで、そしてすぐにcondition failsで をチェックし、current countそれcurrent maxに応じて現在の最大値をリセットします。

このように、すべての反復でチェックされるのではなく、不一致が見つかっmaxた場合にのみチェックされます。

したがって、このコードを試すことができます: -

    // initialize `count = 1`, and `maxnum = Integer.MIN_VALUE`.
    int count = 1;
    int max = 0;
    int maxnum = Integer.MIN_VALUE;

    for(int k = 1;k < length;k++)
     {
         if(arr[k-1] == arr[k]) {
              count++;   // Keep on increasing count till elements are equal

         } else {
             // if Condition fails, check for the current count v/s current max

             if (max < count) {   // Move this from `if` to `else`
                 max = count;
                 maxnum = arr[k - 1];
             }
             count = 1;  // Reset count to 1. As every value comes at least once.
         }
     }

ノート ： -

このアプローチの問題は、2 つの数字が -1と3が同じ回数 (最大) である場合、maxカウントがカウントされることです(それが の後に来て、を含み、 を無視すると3仮定します。ただし、両方を考慮する必要があります。31maxnum31

したがって、基本的に、この問題を処理するためにa を使用して afor loopを維持することはできません。count

より良い方法は、 を作成しMap<Integer, Integer>、そこに各値のカウントを格納することです。そして、sortそのMap上でvalue。

于 2012-11-25T18:03:22.883 に答える
0

最初のアルゴリズムは、配列がソートされている場合にのみ意味があります。

2 番目のアルゴリズムは、間違った場所で count を 0 に設定するだけです。内側のforループに入る前に、count をゼロに設定します。

 for(int h=0;h<length;h++)
 {
  count = 0;
  for(int l=0;l<length;l++)
  {
   if(arr[h] == arr[l])
   {
    count++;
    if(count > max)
    {
     max = count;
     maxnum = arr[h];
    }
   }
  }
 }

countまた、内側のループで毎回チェックする必要はありません。

 max = 0;
 for(int h=0;h<length;h++)
 {
  count = 0;
  for(int l=0;l<length;l++)
  {
   if(arr[h] == arr[l])
    count++;
  }
  if(count > max)
  {
   max = count;
   maxnum = arr[h];
  }
 }
于 2012-11-25T17:57:48.240 に答える
0

私がすぐに確認できるエラーは、すべての要素が異なる場合、最後の最大値は 0 であるということです。ただし、1 である必要があります。新しい要素が発見され、そのカウントは 1 です。

于 2012-11-25T18:03:04.597 に答える
0

あなたの最初のアルゴリズムは私には正しいようです。2 番目のもの (リンクされたコードが使用するもの) は、ループのたびに初期化が必要です。1また、内側のループは毎回開始する必要はありません。から開始できますh + 1:

for(int h=0; h<length; h++)
{
    count = 1; // for the element at arr[h]
    for(int l=h + 1; l<length; l++)
    {
        if(arr[h] == arr[l])
        {
            count++;
        }
    }
    if(count > max)
    {
        max = count;
        maxnum = arr[h];
    }
}

最初のアルゴリズムは、並べ替えられた配列に対してはるかに優れています。並べ替えられていない配列の場合でも、配列 (またはそのコピー) を並べ替えてから、2 番目のアルゴリズムを使用するよりも最初のアルゴリズムを使用する方が安価です。

[1, 1, 2, 2, 3]同点がある場合 ( @Rohit のコメントによる配列など)、最大カウントを持つ最初の値 (ソート順) が検索されることに注意してください。

于 2012-11-25T18:03:44.083 に答える