寻找多数元素的分治算法？

本文介绍了寻找多数元素的分治算法？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

如果数组的一半以上元素相同，则称该数组具有多数元素。是否有分治算法来确定数组是否具有多数元素？

An array is said to have a majority element if more than half of its elements are the same. Is there a divide-and-conquer algorithm for determining if an array has a majority element?

我通常会执行以下操作，但未使用分治方法。我不想使用 Boyer-Moore 算法。

I normally do the following, but it is not using divide-and-conquer. I do not want to use the Boyer-Moore algorithm.

int find(int[] arr, int size) { int count = 0, i, mElement; for (i = 0; i < size; i++) { if (count == 0) mElement = arr[i]; if (arr[i] == mElement) count++; else count--; } count = 0; for (i = 0; i < size; i++) { if (arr[i] == mElement) count++; } if (count > size / 2) return mElement; return -1; }

推荐答案

确实有

为正式起见，我们正在处理多重集（也称为袋子。）在下面，对于多重集 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 。 （这也表明可以通过'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:

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

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:

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

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

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

If S is empty, return none; if S has just one element m, then return (m,1). Otherwise:

Make an even split of S into two halves L and R.

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