c++ - 用于查找多数元素的分而治之算法？

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

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

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

从那里找到(例如)第 25 个和第 75 个百分位数的项目。同样，如果存在多数元素，则至少其中之一需要与中位数具有相同的值。

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

然后继续搜索第 25 个百分位和中位数之间的项目，以及第 75 个百分位和末尾之间的项目。

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

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