c - 如何使用分治法以及如果一个子数组占多数，组合数组占多数的事实来找到多数元素？

Question

在问题中我们被告知算法的关键在于

“当我们深入到单个元素时，那个单一的元素作为其(1 元素)数组的大部分返回。在每个其他级别，它将从其两次递归调用。 这个算法的关键是如果组合数组中有多数元素，那么该元素必须是数组左半部分或数组右半部分中的多数元素。"

我的实现是这样的，可能有很多错误，但总体思路是这样的:

#include <stdio.h>

int merge(int *input, int left, int middle, int right, int maj1, int maj2)
{
    // determine length
    int length1 = middle - left + 1;
    int length2 = right - middle;
    // create helper arrays
    int left_subarray[length1];
    int right_subarray[length2];
    // fill helper arrays
    int i;
    for (i=0; i<length1; ++i)
    {
        left_subarray[i] = input[left + i];
    }
    for (i=0; i<length2; ++i)
    {
        right_subarray[i] = input[middle + 1 + i];
    }
    left_subarray[length1] = 100;
    right_subarray[length2] = 100;
    //both return majority element
    int count1 = 0;
    int count2 = 0;
    for (int i = 0; i < length1; ++i) {
        if (left_subarray[i] == maj1) {
            count1++;
        }
        if (right_subarray[i] == maj1) {
            count1++;
        }
    }
    for (int i = 0; i < length2; ++i) {
        if (right_subarray[i] == maj2) {
            count2++;
        }
        if (left_subarray[i] == maj2) {
            count2++;
        }
    }
    if (count1 > ((length1+length2) - 2)/2){
        return maj1;
    }
    else if (count2 > ((length1+length2) - 2)/2){
        return maj2;
    }
    else
        return 0;
}

int merge_sort(int *input, int start, int end, int maj1, int maj2)
{
    //base case: when array split to one
    if (start == end){
        maj1 = start;
        return maj1;
    }
    else
    {
        int middle = (start + end ) / 2;
        maj1 = merge_sort(input, start, middle, maj1, maj2);
        maj2 = merge_sort(input, middle+1, end, maj1, maj2);
        merge(input, start, middle, end, maj1, maj2);
    }
    return 0;
}

int main(int argc, const char* argv[])
{
    int num;
    scanf("%i", &num);
    int input[num];
    for (int i = 0; i < num; i++){
        scanf("%i", &input[i]);
    }
    int maj;
    int maj1 = -1;
    int maj2 = -1;
    maj = merge_sort(&input[0], 0, num - 1, maj1, maj2);
    printf("%d", maj);
    return 0;
}

这显然不是分而治之。我想知道实现这个的正确方法是什么，这样我可以更好地理解分而治之的实现。我的主要提示是如何合并两个子阵列以将其提升到一个新的水平，但我可能也遗漏了其他部分的一些基本知识。

免责声明:这是一项作业，但我现在正在分析它以加深我的理解。

Answer 1

关于这个特定算法的技巧，以及为什么它以 O(n log n) 时间结束的原因是，您仍然需要迭代要划分的数组以确认多数元素。该部门为这次迭代提供的是正确的候选人。

例如:

[2,1,1,2,2,2,3,3,3,2,2]
          |maj 3| maj 2
    maj 2 | maj None
 <-------------------> still need to iterate 

这隐含在算法语句中:“如果组合数组中有多数元素，则该元素必须是数组左半部分中的多数元素。” “如果”表示仍然需要确认。