求多数元素的分治算法？

Question

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

我通常会执行以下操作，但它不是使用“分而治之”。我不想使用Boyer-Moore算法。

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

Answer 1

一个更简单的分治算法适用于存在多于1/2个相同的元素并且对于某些整数k有n=2^k个元素的情况。

FindMost(A, startIndex, endIndex)
{  // input array A

if (startIndex == endIndex)  // base case
        return A[startIndex]; 
x = FindMost(A, startIndex, (startIndex + endIndex - 1)/2);
y = FindMost(A, (startIndex + endIndex - 1)/2 + 1, endIndex);

if (x == null && y == null) 
    return null;
else if (x == null && y != null) 
    return y;
else if (x != null && y == null) 
    return x;
else if (x != y) 
    return null;
else return x

}

该算法可以修改，使其适用于不是2的指数的n，但必须小心处理边界情况。

Answer 2

是的，它不需要元素有顺序。

从形式上讲，我们处理的是多集（也称为包）在下面，对于多集S，让：

• v（e， S）是元素e在S中的多重性，即它出现的次数（如果e根本不是S的成员，多重性为零。）
• #S是S的基数，即S中计数多重性的元素数。
• 是多集和：如果S=L R，则S包含L和R的所有元素，计算多重性，即v（e； S）=v（e； L）v（e； R）对于任何元素e。（这也表明多重性可以通过“分而治之”来计算。）
• [x]是小于或等于x的最大整数。

S的多数元素m，如果存在的话，就是2v（m；S）的元素

我们把L和R称为s的分裂⊕ R=S和偶数分裂if |#L-#R |≤ 1.也就是说，如果n=#S是偶数，L和R正好有S元素的一半，如果n是奇数，那么一个有基数[n/2]，另一个有基数[n/2]1。

对于S任意拆分为L和R，有两个观察结果：

>

如果L和R中的一个具有多重性k的多数元素m，那么只有当它在另一半具有多重性r时，它才是S的多数元素，具有2（k r）

下面的多数算法返回一对（m，k），表示m是出现k次的多数元素，或者不返回：

>

如果S为空，则不返回任何值；如果S只有一个元素m，则返回（m，1）。否则：

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

设（m，k）=多数（L），如果不是无：

a.设k'=k v（m； R）。

b、 返回（m，k'），如果是2k'

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

a、 设k'=kv（m；L）。

b、 返回（m，k'），如果是2k'

请注意，即使拆分不是偶数，该算法仍然正确。但在实践中，平均分割可能会表现得更好。

补遗

在上面的算法描述中明确了终端情况。一些示例C代码：

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

Answer 3

我至少能看到一种分而治之的方法。

从找到中位数开始，例如使用Hoare的Select算法。如果一个值构成了大多数元素，则中位数必须具有该值，因此我们刚刚找到了我们正在寻找的值。

从那里，找到（例如）第25和第75百分位项目。同样，如果有一个多数元素，那么其中至少有一个元素的值必须与中值相同。

假设你还没有排除大多数元素的存在，你可以继续搜索。例如，假设第75百分位等于中位数，但第25百分位不等于。

在第25个百分位数和第75个百分位数之间继续搜索。

继续查找每个分区的中位数，该分区必须包含与中位数值相同的元素结尾，直到确认或否认多数元素的存在。

顺便说一句：我不太明白Boyer Moore将如何用于这项任务。Boyer Moore是一种在字符串中查找子字符串的方法。