有一种叫做多重集的概念存在，它不需要元素按顺序排列。
严格来说，我们处理的是多重集（也称为袋子）。在下文中，对于一个多重集S，请定义：
- v(e,S) 是元素 e 在集合 S 中出现的次数，即它的重复度（如果 e 不是 S 的成员，则重复度为零。）
- #S 是集合 S 的基数，即考虑重复度的情况下 S 中元素的数量。
- ⊕ 表示多重集和：如果 S = L ⊕ R，则 S 包含所有计算重复度后来自 L 和 R 的元素，即对于任何元素 e，都有 v(e;S) = v(e;L) + v(e;R)。（这也表明可以通过“分而治之”计算重复度。）
- [x] 表示小于或等于 x 的最大整数。
如果存在，则
S的大多数元素
m是满足2
v(
m;
S)>
#S的元素。
如果
L ⊕
R =
S，则称
L和
R为
S的一个分割，并称|
#L -
#R| ≤ 1的分割为偶数分割。也就是说，如果
n=
#S是偶数，则
L和
R恰好有
S的一半元素，如果
n是奇数，则一个集合的基数为[
n/2]，另一个集合的基数为[
n/2]+1。
对于任意
S的分割为
L和
R，有两个观察结果：
如果既没有L也没有R有多数元素，则S也没有：对于任何元素e，2 v（e; S）= 2 v（e; L）+ 2 v（e; R）≤#L+#R=#S。
如果L和R中的一个具有多数元素m，其重复次数为k，则只有当另一半中的重复次数为r时，它才是S的多数元素，其中2（k+r）> #S。
下面的算法majority（S）返回一个二元组（m，k），表示m是具有k个出现次数的多数元素，或者返回none：
- 如果 S 为空，则返回 none；如果 S 只有一个元素 m，则返回 (m,1)。否则：
- 将 S 平均分成两半 L 和 R。
如果 L 不是 none，则令 (m,k) = majority(L):
a. 令 k' = k + v(m;R)。
b. 如果 2 k' > n，则返回 (m,k')。
否则，如果 R 不是 none，则令 (m,k) = majority(R):
a. 令 k' = k + v(m;L)。
b. 如果 2 k' > n，则返回 (m,k')。
- 否则返回 none。
请注意，即使分割不是均匀的，算法仍然是正确的。但是，在实践中，均匀分割很可能表现更好。
补充说明：
在上面的算法描述中明确了终止情况。以下是一些示例C++代码：
struct majority_t {
int m;
size_t k;
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;
}
