錯誤在哪裏？發現大多數

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。