用c++写一个分治法求众数的方法

下面是一个使用分治法求众数的C语言代码：

#include <stdio.h>

int findCandidate(int arr[], int n)
{
    int majIndex = 0, count = 1;
    int i;
    for (i = 1; i < n; i++) {
        if (arr[majIndex] == arr[i])
            count++;
        else
            count--;
        if (count == 0) {
            majIndex = i;
            count = 1;
        }
    }
    return arr[majIndex];
}

int main()
{
    int arr[] = { 3, 3, 4, 2, 4, 4, 2, 4, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int res = findCandidate(arr, n);
    printf("The majority element is %d\n", res);
    return 0;
}

该算法的时间复杂度为O(nlogn)，其中n为数组的长度。算法的基本思路是：将数组分成两个部分，递归地求解每个部分的众数，然后将两个部分的众数进行比较，保留出现次数更多的那个作为整个数组的众数。如果递归到只有一个元素，那么该元素就是众数。

相关问题

用c++写一个分治法求众数

以下是一种实现方法：

#include <stdio.h>

// 用分治法求众数
int majority(int arr[], int left, int right) {
    if (left == right) { // 只有一个元素，直接返回该元素
        return arr[left];
    }

    int mid = (left + right) / 2; // 计算中间位置

    // 递归求左右两边的众数
    int left_majority = majority(arr, left, mid);
    int right_majority = majority(arr, mid+1, right);

    // 如果左右两边的众数相同，则直接返回该众数
    if (left_majority == right_majority) {
        return left_majority;
    }

    // 否则统计左右两边的众数出现的次数，返回出现次数较多的那个众数
    int left_count = 0;
    int right_count = 0;
    for (int i = left; i <= right; i++) {
        if (arr[i] == left_majority) {
            left_count++;
        } else if (arr[i] == right_majority) {
            right_count++;
        }
    }
    return left_count > right_count ? left_majority : right_majority;
}

int main() {
    int arr[] = {1, 1, 2, 2, 2, 3, 3, 3, 3, 3};
    int n = sizeof(arr) / sizeof(int);
    int majority_num = majority(arr, 0, n-1);
    printf("The majority number is: %d\n", majority_num);
    return 0;
}

该代码采用递归的方式实现分治法求众数，具体实现流程如下：

1. 若当前区间只有一个元素，则直接返回该元素。
2. 分治将当前区间分成左右两部分，分别递归求解左右两边的众数。
3. 若左右两边的众数相同，则直接返回该众数。
4. 否则统计左右两边的众数出现的次数，返回出现次数较多的众数。

该算法的时间复杂度为 O(nlogn)，空间复杂度为 O(logn)。

用c++写分治法求众数

以下是用C++实现分治法求众数的代码：

#include <iostream>
#include <vector>
using namespace std;

int majorityElement(vector<int>& nums) {
    if (nums.empty()) {
        return -1;
    }
    if (nums.size() == 1) {
        return nums[0];
    }
    vector<int> left(nums.begin(), nums.begin() + nums.size() / 2);
    vector<int> right(nums.begin() + nums.size() / 2, nums.end());
    int left_majority = majorityElement(left);
    int right_majority = majorityElement(right);
    if (left_majority == right_majority) {
        return left_majority;
    }
    int left_count = 0, right_count = 0;
    for (int num : nums) {
        if (num == left_majority) {
            left_count++;
        } else if (num == right_majority) {
            right_count++;
        }
    }
    if (left_count > right_count) {
        return left_majority;
    } else {
        return right_majority;
    }
}

int main() {
    vector<int> nums = {1, 2, 3, 2, 2, 2, 5, 4, 2};
    int majority = majorityElement(nums);
    cout << "The majority element is " << majority << endl;
    return 0;
}

该算法的时间复杂度为O(nlogn)，空间复杂度为O(logn)。