使用 C 使用分而治之法查找数组中的多数元素

Question

我正在编写一个算法来查找数组中的多数元素。基本上，如果一个元素在数组中至少出现 length/2，则它是多数元素。否则，该数组没有多数元素。

我不是很懂C，所以我在Python中找到了相同的解决方案，并尝试转换它。但是，我得到的结果有一些不寻常的错误。我的算法是这样的：

#include <stdio.h>
int find_majority_element(int arr[], int length);

int main()
{
    int arr[] = { 12, 3, 1, 1, 3, 4, 2, 2, 9, 6, 2, 1, 2 };
    int length = sizeof(arr)/sizeof(int);

    int result = find_majority_element(arr, length);

    if (result == -1) {
        printf("None");
    } else {
        printf("%d", result);
    }
    return 0;
}

int find_majority_element(int arr[], int length) {

    if (length == 2) {
        if (arr[0] == arr[1]) {
            return arr[0];
        } else {
            return -1;
        }
    } else if (length == 1) {
        return arr[0];
    }

    int *leftHalf = arr;
    int *rightHalf = arr + length/2;

    int element1 = find_majority_element(leftHalf, length/2);
    int element2 = find_majority_element(rightHalf, length/2);

    if (element1 == -1 && element2 >= 0) {
        return element2;
    } else if (element2 == -1 && element1 >= 0) {
        return element1;   
    }

    if (element1 == element2) {
        return element1;
    } else {
        return -1;
    }

}

这给了我意想不到的结果，考虑到我刚刚转换了另一种算法，这很奇怪。有问题的算法可以在这里找到：

Link

有什么帮助吗？谢谢

编辑

对于给定的输入，多数元素显示为 2。这显然是错误的。

Answer 1

当 length 为奇数时，代码不会检查整个右半部分。

// int element2 = find_majority_element(rightHalf, length/2);
int element2 = find_majority_element(rightHalf, length - length/2);

总体而言，OP 的方法对于 未排序的 数组 . Review Majority Element 替代解决方案是不正确的。

学究角：代码有问题 length <= 0。

使用 C 使用分而治之法查找数组中的多数元素

Finding the majority element in an array using C using Divide and Conquer

c

algorithm

divide-and-conquer