关小刷刷题02——Leetcode 169. Majority Element 方法2和3

题目

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）。
同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。