如何使用分而治之以及如果一个子阵列占多数，组合阵列占多数以找到多数元素的事实？

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

这显然不是分而治之的。我想知道实现这个的正确方法是什么，所以我可以更好地理解分而治之的实现。我的主要抱怨是如何合并两个子阵列以将其升级到下一个级别，但我可能也错过了其他部分的基本内容。

免责声明：本WAS适用于作业，但我现在正在分析它以进一步理解。

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 

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