Leetcode No.169 Majority Element(c++实现)
2021/7/14 22:12:51
本文主要是介绍Leetcode No.169 Majority Element(c++实现),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1. 题目
1.1 英文题目
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
1.2 中文题目
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
1.3输入输出
输入 | 输出 |
---|---|
nums = [3,2,3] | 3 |
nums = [2,2,1,1,1,2,2] | 2 |
1.4 约束条件
- n == nums.length
- 1 <= n <= 5 * 104
- -231 <= nums[i] <= 231 - 1
2. 分析
2.1 Moore's voting
每次都找出一对不同的元素,从数组中删掉,直到数组为空或只有一种元素。 不难证明,如果存在元素e出现频率超过半数,那么数组中最后剩下的就只有e。代码如下:
class Solution { public: int majorityElement(vector<int>& nums) { // 摩尔投票法 int candidate = nums[0]; // 候选值 for (unsigned int i = 1, count = 1; i < nums.size(); i++) { if (count == 0) candidate = nums[i]; count += (count == 0 || candidate == nums[i]) ? 1 : -1; } return candidate; } };
参考自:https://blog.csdn.net/huanghanqian/article/details/74188349
2.2 哈希表法
建立一个哈希表,存储元素与其出现次数;遍历给定的数组,增加其哈希表中对应的次数;如果有一个次数大于长度/2,记录答案。代码如下:
class Solution { public: int majorityElement(vector<int>& nums) { // 哈希表法 unordered_map<int, int> hash; int ans; int length = nums.size(); for (int i = 0; i < length; i++) { hash[nums[i]]++; if (hash[nums[i]] > length / 2) { ans = nums[i]; break; } } return ans; } };
参考自:https://blog.csdn.net/weixin_44176696/article/details/104445717
2.3 位操作法
把数字都作为二进制处理,每个二进制位上的n个bit相加看是否大于n/2,大于的话这一位上是1,小于的话就是0,把32位都这么处理完即可。具体代码如下:
class Solution { public: int majorityElement(vector<int>& nums) { int i,j,count,major=0; for(i=0;i<32;i++) { for(j=0,count=0;j<nums.size();j++) { if((nums[j]>>i&1)==1) count++; } if(count>nums.size()/2) major+=(1<<i); } return major; } };
参考自:https://www.cnblogs.com/wdfwolf3/p/5490887.html
位操作解读:https://www.cnblogs.com/zhoug2020/p/4978822.html
这篇关于Leetcode No.169 Majority Element(c++实现)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-07fastcgi 是什么-icode9专业技术文章分享
- 2024-10-07fastcgi 的详细使用教程介绍-icode9专业技术文章分享
- 2024-10-07git如何更新单个文件到本地-icode9专业技术文章分享
- 2024-10-07如何使用ASM(Abstract Syntax Tree Manipulation)技术来修改第三方AAR依赖中的函数-icode9专业技术文章分享
- 2024-10-07Activity 跳转时间耗时很长怎么优化解决-icode9专业技术文章分享
- 2024-10-07Androud Toast 有哪些常用的第三方组件-icode9专业技术文章分享
- 2024-10-07在viewmodel中怎么使用 mmkv?-icode9专业技术文章分享
- 2024-10-07MMKV.defaultMMKV() 是单例模式吗?-icode9专业技术文章分享
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享