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, 因为您的数组已排序。第二个算法不必要地遍历数组两次。

现在你first algorithm几乎是正确的，但它有两个问题： -

  • 第一个问题是您正在设置count = 0，在其他部分，它应该设置为1。因为每个元素至少出现一次。
  • 其次，您不需要max每次都在if. 只要 increment count，直到if-condition满足 ，并尽快condition fails，检查current countwith 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.
         }
     }

笔记 ： -

这种方法的问题是，如果两个数字说 -1和3，出现相同的次数 - 这是最大值，那么max计数将被计算3（假设3在 之后1，并且maxnum将包含3和忽略1。但它们都应该被考虑。

所以，基本上，你不能使用 afor loop和维护 acount来解决这个问题。

更好的方法是创建一个Map<Integer, Integer>, 并将每个值的计数存储在其中。然后在sort那个。Mapvalue

于 2012-11-25T18:03:22.883 回答
0

只有对数组进行了排序，您的第一个算法才有意义。

您的第二个算法只是在错误的地方将计数设置为零。您想在进入内部for循环之前将计数设置为零。

 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 而不是 0，作为新元素被发现，其计数为 1。

于 2012-11-25T18:03:04.597 回答
0

你的第一个算法对我来说看起来是正确的。第二个（这是您的链接代码使用的）每次循环都需要一些初始化。此外，内循环不需要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];
    }
}

第一个算法对于排序数组要好得多。即使对于未排序的数组，对数组（或它的副本）进行排序然后使用第一个算法而不是使用第二个算法也会更便宜。

请注意，如果存在关联（例如根据[1, 1, 2, 2, 3]@Rohit 的评论对于数组），这将找到具有最大计数的第一个值（按排序顺序）。

于 2012-11-25T18:03:44.083 回答