LeetCode 热题 100_多数元素（97_169_简单_C++）（哈希表；排序）

标题形貌：

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组黑白空的，并且给定的数组总是存在多数元素。
输入输出样例：

示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums <= 109
进阶：实验计划时间复杂度为 O(n)、空间复杂度为 O(1) 的算法办理此问题。
题解：

解题思绪：

思绪一（哈希表）：

1、我们通过数组中出现次数 大于 ⌊ n/2 ⌋ 的元素只能为一个，推断出答案只有一个元素（给定的数组总是存在多数元素）。则我们可以利用哈希表对每个元素举行计数，记录其中出现次数最大的元素。
2、复杂度分析：
① 时间复杂度：O(n)，其中 n 是数组的长度，只遍历了一遍数组。
② 空间复杂度：O(n)，哈希表所利用的空间。
思绪二（排序）：

1、当我们对数组举行排序后，出现次数最大的元素会聚集在一起，且大于n/2，所以取中间元素则为出现次数最大的元素。
2、复杂度分析
① 时间复杂度：O(n log n)，快排。
② 空间复杂度：O(log n)，快排利用的空间。
代码实现

代码实现（思绪一（哈希表））：

1. class Solution1 {
2. public:
3.     // 该函数返回数组中出现次数最多的元素
4.     int majorityElement(vector<int> &nums) {
5.         int max_frequency = 0; // 存储最大出现次数
6.         int most_frequent_element; // 存储出现次数最多的元素
7.         unordered_map<int, int> mp; // 用哈希表存储每个元素的出现次数
8.         
9.         // 遍历数组
10.         for (auto &i : nums) {
11.             mp[i]++; // 增加当前元素的出现次数
12.             if (mp[i] > max_frequency) { // 如果当前元素的出现次数大于当前最大次数
13.                 max_frequency = mp[i]; // 更新最大出现次数
14.                 most_frequent_element = i; // 更新出现次数最多的元素
15.             }
16.         }
18.         return most_frequent_element; // 返回出现次数最多的元素
19.     }
20. };

复制代码

代码实现（思绪二（排序））：

1. class Solution2 {
2. public:
3.     // 该函数返回数组中出现次数最多的元素
4.     int majorityElement(vector<int> &nums) {
5.         //快速排序
6.         sort(nums.begin(),nums.end());
7.         return nums[nums.size()/2]; // 返回出现次数最多的元素
8.     }
9. };

复制代码

以思绪二为例举行调试

1. #include<iostream>#include<vector>#include<unordered_map>#include<algorithm>using namespace std;class Solution2 {
2. public:
3.     // 该函数返回数组中出现次数最多的元素
4.     int majorityElement(vector<int> &nums) {
5.         //快速排序
6.         sort(nums.begin(),nums.end());
7.         return nums[nums.size()/2]; // 返回出现次数最多的元素
8.     }
9. };
10. int main(int argc, char const *argv[]){    vector<int> nums={3,3,4};    Solution2 s;    cout<<s.majorityElement(nums);    return 0;}

复制代码

LeetCode 热题 100_多数元素（97_169)原题链接
欢迎各人和我沟通交流(✿◠‿◠)

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告