C++实现众数算法 |21xrx.com

C++实现众数算法

2023-06-22 04:58:55 深夜i 20 0

C++ 众数算法

众数是一个数组中出现频率最高的元素，C++提供了多种方法来实现众数算法。下面介绍两个常见的方法。

第一种方法是使用哈希表。哈希表是一种数据结构，用于快速查找和插入元素。我们可以使用一个哈希表来存储数组中每个元素出现的次数，然后找到出现频率最高的元素。具体实现如下：

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int findMode(vector<int>& nums) {
  unordered_map<int, int> count;
  int mode = nums[0], maxCount = 0;
  for (int num : nums) {
    count[num]++;
    if (count[num] > maxCount) {
      mode = num;
      maxCount = count[num];
    }
  }
  return mode;
}
int main() {
  vector<int> nums = 2;
  int mode = findMode(nums);
  cout << mode << endl; // 输出3
  return 0;
}

第二种方法是使用排序。我们可以将数组排序，然后比较相邻元素的值来确定众数。具体实现如下：

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int findMode(vector<int>& nums) {
  sort(nums.begin(), nums.end());
  int mode = nums[0], count = 1, maxCount = 1;
  for (int i = 1; i < nums.size(); i++) {
    if (nums[i] == nums[i-1]) {
      count++;
    } else {
      if (count > maxCount) {
        mode = nums[i-1];
        maxCount = count;
      }
      count = 1;
    }
  }
  if (count > maxCount) {
    mode = nums[nums.size()-1];
  }
  return mode;
}
int main() {
  vector<int> nums = {1, 2, 2, 3, 3, 3};
  int mode = findMode(nums);
  cout << mode << endl; // 输出3
  return 0;
}

这两种方法都具有线性时间复杂度，即O(n)，其中n是数组的长度。使用哪种方法取决于实际情况，需要根据数组的规模和其他要求进行选择。

上一篇: idea打包java可执行jar包

下一篇: 如何在C++中打出反斜杠？

评论区

相似文章