关小刷刷题02——Leetcode 169. Majority Element 方法2和3
关小刷刷题02——Leetcode 169. Majority Element 方法2和3
WZEARW
发布于 2018-04-08 17:10:53
发布于 2018-04-08 17:10:53
题目
169. Majority Element Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array.
方法2
方法2：把每个数出现的次数用一个map记录下来，key是数组中的数，value是该数出现的次数。因为最后想找出现次数最大的数，也就是找最大value对应的key值。
class Solution {
public:
int majorityElement(vector<int>& nums) {
map<int, int>temp;
for(int i=0; i<nums.size(); i++)
{
temp[nums[i]]++;
}
int number=temp.begin()->first;
int count=temp.begin()->second;
for(auto it=temp.begin(); it!=temp.end(); it++)
{
if(it->second>count)
{
number=it->first;
count=it->second;
}
}
return number;
}};我们对上面的代码进行了优化：
class Solution {
public:
int majorityElement(vector<int>& nums) {
map<int, int>temp;
for(int x:nums)
{
if (++temp[x]>nums.size()/2)
{
return x;
}
}
}
};方法3
方法3：可以采用类似于下棋对子的方法。从头开始遍历数组，只要有不一样的两个数就相互对掉，那么最后剩下的那个数就是所求解。这种方法相比于前两种方法很巧妙，最不容易想到。但是时间复杂度o(n)，相比于方法一的sort快排o(nlogn)降低了时间复杂度。不利用额外空间，相比于方法二的map降低了空间复杂度。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int count=1;
int value=nums[0];
for(int i=1; i<nums.size(); i++)
{
if(count==0)
{
value= nums[i];
count++;
}
else
{
if(value==nums[i])
count++;
else
count--;
}
}
return value;
}
};点击专知主题Leetcode: http://www.zhuanzhi.ai/#/topic/2001901869867117。查看更多关于关关的Leetcode的刷题日记。
以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2017-09-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录