用c++写一个众数问题

可以使用以下代码解决众数问题：

#include <stdio.h>

int main() {
    int arr[] = {1, 2, 3, 4, 4, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(int);
    int mode = arr[0];
    int count = 1;
    int maxCount = 1;
    
    for (int i = 1; i < n; i++) {
        if (arr[i] == arr[i-1]) {
            count++;
        } else {
            if (count > maxCount) {
                maxCount = count;
                mode = arr[i-1];
            }
            count = 1;
        }
    }
    
    if (count > maxCount) {
        maxCount = count;
        mode = arr[n-1];
    }
    
    printf("The mode is %d\n", mode);
    
    return 0;
}

这段代码通过遍历数组来找到最常出现的数字。

相关问题

用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)。