c++ - N/3 重复次数

Question

问题是找出数组中是否有任何整数出现超过 n/3 次。该解决方案基于摩尔的投票算法（如果我们用与 e 不同的所有其他元素来抵消元素 e 的每次出现，那么如果 e 是多数元素，则 e 将一直存在。）

    findCandidate(a[], size)
            1.  Initialize index and count of majority element
                 maj_index = 0, count = 1
            2.  Loop for i = 1 to size – 1
                 (a) If a[maj_index] == a[i]
                          count++
                 (b) Else
                          count--;
                 (c) If count == 0
                          maj_index = i;
                          count = 1
            3.  Return a[maj_index]

现在我们只需要检查候选元素的计数是否大于 n/2。

在寻找多数元素的情况下，这种寻找多数元素候选者的方法被理解为，即至少比其他元素重复更多的数字，即使是一个候选者，但它在这个问题中的应用尚不清楚。

据说您从数组中有 3 个不同的元素，如果您从数组中删除它们，您的答案不会改变，并且保留 2 个元素及其计数。

在大多数情况下，我们维护一个是多数的候选者，但是为什么不管需要多少次更改，这里都维护两个。例子：n=3/4/5大于1次，n=6/7/8大于2次等。伪代码如下：

        When we encounter a new element, there are 3 cases possible :

              1)We don’t have 2 elements yet. So add this to the list with count as 1.

              2)This element is different from the existing 2 elements. As we said before, we 
                have 3 distinct numbers now. Removing them does not change the answer. So 
                decrements 1 from count of 2 existing elements. If their count falls to 0, 
                obviously its not a part of 2 elements anymore.

              3)The new element is same as one of the 2 elements. Increment the count of that 
                element.

代码如下：

              for (int i = 0; i < n; i++) { 

                      // if this element is previously seen,  
                      // increment count1. 
                       if (first == arr[i]) 
                           count1++; 

                     // if this element is previously seen,  
                     // increment count2. 
                       else if (second == arr[i]) 
                           count2++; 

                       else if (count1 == 0) { 
                           count1++; 
                           first = arr[i]; 
                       } 

                       else if (count2 == 0) { 
                            count2++; 
                            second = arr[i]; 
                        } 

                       // if current element is different from 
                       // both the previously seen variables,  
                       // decrement both the counts. 
                        else { 
                             count1--; 
                             count2--; 
                       } 
                } 

                count1 = 0; 
                count2 = 0; 

               // Again traverse the array and find the 
               // actual counts. 
              for (int i = 0; i < n; i++) { 
                       if (arr[i] == first) 
                              count1++; 

                        else if (arr[i] == second) 
                               count2++; 
} 

                     if (count1 > n / 3) 
                            return first; 

                    if (count2 > n / 3) 
                            return second; 



         Consequently, the answer will be one of the 2 elements left behind. If they are 
         not the answer, then there is no element with count > N / 3

为什么候选人被考虑是两个和资格标准？

标签： c++algorithmdata-structuresarray-algorithms