思路一:数组按序排列,中间的数肯定是出现次数大于n/2的数 仔细推理一下就可以得出规律
思路二:哈希表 (map)
哈希表相关知识点解释:哈希表简单来说就是建立key到value的映射。 就题而言就是数组的数值(key )与数值在数组中出现的次数(value)的映射
C++中用map<int,int>即可简单建立一个哈希表。
1 class Solution { 2 public: 3 int majorityElement(vector<int>& nums) { 4 map<int,int> m; 5 for(int i=0;i<nums.size();i++) 6 { 7 m[nums[i]]=0; //初始化 8 } 9 for(int i=0;i<nums.size();i++) 10 { 11 m[nums[i]]++; 12 if(m[nums[i]]>nums.size()/2) 13 { 14 return nums[i]; 15 } 16 } 17 return -1; 18 19 20 } 21 };
View Code
原文链接: https://www.cnblogs.com/nxnslc-blog/p/12393714.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/333036
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!