确实有

为正式起见，我们正在处理多重集（也称为袋子。）在下面，对于多重集 S ，让：

To be formal, we're dealing with multisets (also called bags.) In the following, for a multiset S, let:

• v （ e ， S ）是元素的多重性e S 中的e ，即它出现的次数（如果 e 不是 S 的成员，则多重性为零


• #S 是 S 的基数，即 S 中的元素数


• ⊕是多集和：如果 S = L ⊕ R ，则 S 包含计数重复性的 L 和 R 的所有元素，即 v （ e ; S ）= v （ e ; L ）+ v （ e ; R ）用于任何元素 e m>。 （这也表明可以通过'divide-and-conquer'来计算多重性。）


• [ x ]是小于或等于的最大整数 x 。

• v(e,S) be the multiplicity of an element e in S, i.e. the number of times it occurs (the multiplicity is zero if e is not a member of S at all.)
• #S be the cardinality of S, i.e. the number of elements in S counting multiplicity.
• ⊕ be the multiset sum: if S = L ⊕ R then S contains all the elements of L and R counting multiplicity, i.e. v(e;S) = v(e;L) + v(e;R) for any element e. (This also shows that the multiplicity can be calculated by 'divide-and-conquer'.)
• [x] be the largest integer less than or equal to x.

S的多数元素 m （如果存在）是那个元素，使得2 v （ m ; S ）> #S 。

我们称​​ L 和 R 为 S 如果 L ⊕ R = S ，并且如果| #L em>- #R | ≤1。也就是说，如果 n = #S 是偶数，则 L 和 R 恰好具有一半的元素 S 的值，如果 n 是奇数，则一个具有基数[ n / 2]，另一个具有基数[ n / 2] +1。

Let's call L and R a splitting of S if L ⊕ R = S and an even splitting if |#L - #R| ≤ 1. That is, if n=#S is even, L and R have exactly half the elements of S, and if n is odd, than one has cardinality [n/2] and the other has cardinality [n/2]+1.

将 S 任意分割为 L 和 R ，有两个观察值：

For an arbitrary split of S into L and R, two observations:

1. 如果 L 和 R 具有多数元素，则 S 不能：对于任何元素 e ，2 v （ e ; S ）= 2 v （ e ; L ）+ 2 v （ e ; R ）≤ #L + #R = #S 。

1. If neither L nor R has a majority element, then S cannot: for any element e, 2 v(e;S) = 2 v(e;L) + 2 v(e;R) ≤ #L + #R = #S.

如果 L 和 R 之一的多数元素 m 具有多重性 k ，则只有当它的另一半具有多重性 r 且具有2（ k + r ）> #S 。

If one of L and R has a majority element m with multiplicity k, then it is the majority element of S only if it has multiplicity r in the other half, with 2(k+r) > #S.

算法多数（ S ）belo w返回一对（ m ， k ），表示 m 是出现 k 的多数元素，或 none ：

The algorithm majority(S) below returns either a pair (m,k), indicating that m is the majority element with k occurrences, or none:

1. 如果 S 为空，则返回 none ;如果 S 只有一个元素 m ，则返回（ m ，1）。否则：


2. 将 S 均匀分成两半 L 和 R 。



3. 让（ m ， k ）= 多数（ L ） ，如果不是 none ：

1. If S is empty, return none; if S has just one element m, then return (m,1). Otherwise:
2. Make an even split of S into two halves L and R.

3. Let (m,k) = majority(L), if not none:

a。设 k' = k + v （ m ; R ）。

a. Let k' = k + v(m;R).

b。如果2 k'> n ，则返回（ m ， k'）。

b. Return (m,k') if 2 k' > n.

否则让（ m ， k ）= 多数（ R ） ，如果不是 none ：

Otherwise let (m,k) = majority(R), if not none:

a。设 k' = k + v （ m ; L ）。

a. Let k' = k + v(m;L).

b。如果2 k'> n ，则返回（ m ， k'）。

b. Return (m,k') if 2 k' > n.

请注意，即使分裂不是均匀的。尽管在实践中平均分配可能会更好。

Note that the algorithm is still correct even if the split is not an even one. Splitting evenly though is likely to perform better in practice.

附录

制造在上述算法说明中明确显示的终端案例。一些示例C ++代码：

Made the terminal case explicit in the algorithm description above. Some sample C++ code:

struct majority_t {
    int m; // majority element
    size_t k; // multiplicity of m; zero => no majority element

    constexpr majority_t(): m(0), k(0) {}
    constexpr majority_t(int m_,size_t k_): m(m_), k(k_) {}

    explicit operator bool() const { return k>0; }
};

static constexpr majority_t no_majority;

size_t multiplicity(int x,const int *arr,size_t n) {
    if (n==0) return 0;
    else if (n==1) return arr[0]==x?1:0;

    size_t r=n/2;
    return multiplicity(x,arr,r)+multiplicity(x,arr+r,n-r);
}

majority_t majority(const int *arr,size_t n) {
    if (n==0) return no_majority;
    else if (n==1) return majority_t(arr[0],1);

    size_t r=n/2;
    majority_t left=majority(arr,r);
    if (left) {
        left.k+=multiplicity(left.m,arr+r,n-r);
        if (left.k>r) return left;
    }

    majority_t right=majority(arr+r,n-r);
    if (right) {
        right.k+=multiplicity(right.m,arr,r);
        if (right.k>r) return right;
    }

    return no_majority;
}