错误在哪里？发现大多数

Question

我想找到的大多数阵列（数字出现的大部分时间）。 我有一个排序后的数组，并使用这些循环：

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; 
    } 
} 

它们similiar。当我在小阵列上尝试它们时，一切似乎都没有问题。但在长的运行数组N个元素0 < = N < = 500000，每个元件K 0 < = K < = 10^9他们给错误的答案。 这里是错误http://ideone.com/y2gvnX解决方案。我知道有更好的算法可以找到大多数，但我只需要知道我的错误在哪里。

我真的无法找到它:(可能喜欢帮助！

Answer 1

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

第一种算法是多的有序阵列更好。即使对于未排序的数组，排序数组（或其副本）也会更便宜，然后使用第一种算法而不是第二种算法。

请注意，如果存在关系（例如根据@ Rohit的评论为数组[1, 1, 2, 2, 3]），则会查找具有最大计数的第一个值（按排序顺序）。

Answer 2

如果数组进行排序您的第一个算法才有意义。

你的第二个算法只是在错误的地方设置计数为零你要你进入内环路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]; 
    } 
} 

Answer 3

的错误，我可以很容易地看到的是，如果所有元素都是不同的，那么最大的末尾为0 但是它必须是1 所以，当你在“其他”的情况下更新计数，将其更新到1而不是0，作为一个新的元素已经被发现，其计数为1

Answer 4

首先，你应该使用first algorithm，为您的数组进行排序。第二种算法不必要地通过阵列两次。

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

• 第一个问题是您要设置count = 0，在其他部分， 而是应设置为1。因为每个元素至少有一次 。
• 其次，你不需要每次都设置max你if。只需要 increment count，直到if-condition得到满足，并且尽快 为​​，请检查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. 
     } 
    } 

注： -

这种方法的问题是，如果两个数字会说话 - 1和3，来的人数相等倍 - 这是最大，则max计数将计数3（假设3自带1后，和maxnum将包含3并忽略1。但他们都应该考虑。

因此，基本上，您不能使用for loop并维护count来处理此问题。

更好的方法是创建一个Map<Integer, Integer>，并将每个值的计数存储在那里。然后sort即Map对value。