C++求众数 |21xrx.com

C++求众数

2023-07-02 18:49:14 深夜i -- --

C++ 求众数统计数组

在C++中，寻找一个数列中的众数是一个经常出现的问题。众数指的是在数列中出现次数最多的数，可能有多个。那么，我们怎样在C++中求解一个数列的众数呢？下面我将介绍一种常见的方法。

一、暴力法

最朴素的方法便是直接进行遍历，找到出现次数最多的数即可。具体来说，我们可以通过两个嵌套的循环，分别枚举数列中的每一个数，然后统计该数在数列中出现的次数。在统计时，我们可以设置一个max变量来记录出现次数最多的数，并随时更新该变量。最后，我们返回max即可。

但是，这种方法的时间复杂度为O(n^2)，不适用于大规模的数据处理。因此，我们需要寻找更快速的方法来求解众数。

二、哈希表

哈希表是一种效率高、实现简单的数据结构，十分适用于求解众数的问题。

哈希表可以将一个数列中的所有元素和它们出现的次数进行存储。我们可以通过遍历数列中的每一个元素，然后在哈希表中对相应的值进行加一的操作，从而统计每个元素在数列中出现的次数。

最后，我们只需要寻找哈希表中值最大的元素，即为数列中的众数。时间复杂度为O(n)，极大地提高了程序的效率。

以下是代码实现：


int majorityElement(vector<int>& nums) {
  unordered_map<int, int> mp;
  int max_val = 0, max_key = 0;
  for (int i = 0; i < nums.size(); i++) {
    mp[nums[i]]++;
    if (mp[nums[i]] > max_val) {
      max_val = mp[nums[i]];
      max_key = nums[i];
    }
  }
  return max_key;
}

此处用到了C++ STL库中的unordered_map，用来实现哈希表的相关操作。

三、摩尔投票算法

摩尔投票算法是一种高效的求众数的算法，它的时间复杂度为O(n)，空间复杂度为O(1)。

该算法的思路是遍历数列中所有的元素，设当前元素为candidate，count为计数器，则进行如下操作：

1. 若count为0，则将当前元素设为candidate。

2. 若当前元素与candidate相等，则将count加一。

3. 若当前元素与candidate不相等，则将count减一。

最后，candidate即为数列的众数。

该算法的正确性来源于众数出现的次数大于其余元素出现的次数和，因此当我们删除一对不相同的元素时，众数出现的次数并不会改变。

以下是代码实现：


int majorityElement(vector<int>& nums) {
  int candidate = 0, count = 0;
  for (int num : nums) {
    if (count == 0) candidate = num;
    count += (num == candidate) ? 1 : -1;
  }
  return candidate;
}

综上所述，我们可以在C++中使用暴力法、哈希表和摩尔投票算法三种方法来求解一个数列的众数，每种方法都具有其独特的优势和适用条件。在实际的编程过程中，我们可以选择合适的方法来解决对应的问题，从而提高程序的效率和可读性。

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

下一篇: C++输出流函数：让编程更高效的输出方式

评论区

()

相似文章