C++ 分治算法求解众数问题

{"title":"C++ 分治算法求解众数问题","description":"本文介绍了使用分治算法解决众数问题的C++代码。给定一个包含n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。代码使用分治算法递归地求解左右子集的众数，并根据结果判断整个集合的众数。","keywords":"众数, 分治算法, C++, 代码, 多重集","content":""给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S={1，2，2，2，3，5}。多重集S的众数是2，其重数为3。对于给定的由n 个自然数组成的多重集S，计算S的众数及其重数。如果出现多个众数，请输出最小的那个。\n\nInput\n输入数据的第1行是多重集S中元素个数n（n<1300000）；接下来的n行中，每行有一个最多含有5位数字的自然数，。\n\nOutput\n输出数据的第1行给出众数，第2行是重数。\n请使用分治算法解决上面问题，并给出c++代码内容：以下是使用分治算法解决众数问题的C++代码：\n\ncpp\\n#include <iostream>\\n#include <vector>\\n#include <unordered_map>\\n\\nusing namespace std;\\n\\n// 分治算法求众数\\npair<int, int> majorityElement(vector<int>& nums, int left, int right) {\\n // 边界情况，只有一个元素\\n if (left == right) {\\n return make_pair(nums[left], 1);\\n }\\n\\n // 分治求解左右子集的众数\\n int mid = left + (right - left) / 2;\\n pair<int, int> leftMajority = majorityElement(nums, left, mid);\\n pair<int, int> rightMajority = majorityElement(nums, mid + 1, right);\\n\\n // 如果左右子集的众数相同，则该数为整个集合的众数\\n if (leftMajority.first == rightMajority.first) {\\n return make_pair(leftMajority.first, leftMajority.second + rightMajority.second);\\n }\\n\\n // 否则，统计左右子集的众数出现的次数\\n int leftCount = 0, rightCount = 0;\\n for (int i = left; i <= right; i++) {\\n if (nums[i] == leftMajority.first) {\\n leftCount++;\\n } else if (nums[i] == rightMajority.first) {\\n rightCount++;\\n }\\n }\\n\\n // 返回出现次数较多的众数\\n if (leftCount > rightCount) {\\n return leftMajority;\\n } else {\\n return rightMajority;\\n }\\n}\\n\\nint main() {\\n int n;\\n cin >> n;\\n \\n vector<int> nums(n);\\n for (int i = 0; i < n; i++) {\\n cin >> nums[i];\\n }\\n\\n pair<int, int> result = majorityElement(nums, 0, n - 1);\\n cout << result.first << endl;\\n cout << result.second << endl;\\n\\n return 0;\\n}\\n\n\n该代码使用了分治算法来求解众数问题。首先，定义了一个名为majorityElement的函数，该函数接收一个包含n个元素的向量nums以及左右边界left和right作为参数。函数会根据边界情况进行处理，如果左右边界相等，则返回该元素及其重数。否则，将问题分为两个子问题，分别求解左子集和右子集的众数。然后，判断左子集和右子集的众数是否相同，如果相同，则该数为整个集合的众数。如果不相同，则统计左右子集的众数出现的次数，返回出现次数较多的众数。最后，在main函数中读取输入数据，调用majorityElement函数求解众数问题，并输出结果。\n