[C++知识库]easy 多数元素 哈希表 摩尔投票法

哈希表：

c++

int i =0; int a=i++;
a = i = 0 后, i++, i=1

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map <int,int> mp;  // 哈希表
        for(auto num : nums){
            mp[num]++;
            int temp=mp[num] ;  // 不能写成 int temp=mp[num]++, 即先temp=mp[num], 再mp[num]++， temp与mp[num] 没有关系
            if( temp > nums.size()/2){
                return num;
            }
        }
        return -1;
    }
};

简洁写法

只能用 ++mp[num] 不能用 mp[num]++原因：
int i=0; (i++ = 0, i=1)
int i=0; (++i = 1, i=1)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map <int,int> mp;  // 哈希表
        for(auto num : nums){
            if( ++mp[num] > nums.size()/2){
                return num;
            }
        }
        return -1;
    }
};

python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        d = {}  # python 哈希表即字典
        for i in nums:
            if i in d.keys():
                d[i] += 1
            else:
                d[i] = 1
                
            if d[i] > len(nums)/2:
                return i

        return -1

注意： 出错写法

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dic={}
        for num in nums:
            dic[num] += 1
            if dic[num] > len(nums)/2:
                return num

        return -1

出错原因：
使用普通的字典时，用法一般是dict={},添加元素的只需要dict[element] =value即，调用的时候也是如此，dict[element] = xxx,但前提是element字典里，如果不在字典里就会报错，

更正： 哈希字典初始化 defaultdict
defaultdict 的作用是在于，当字典里的 key 不存在但被查找时，返回的不是 keyError 而是一个默认值。比如list对应[ ]，str对应的是空字符串，set对应set( )，int对应0

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dic = defaultdict(int)
        for num in nums:
            dic[num] += 1
            if dic[num] > len(nums)/2:
                return num

        return -1

简洁写法：

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dic = defaultdict(int)
        for num in nums:
            dic[num] += 1
        #返回出现次数最多的num, 即返回字典中最大value对应的key
        return max(dic, key=dic.get)

排序：

因为出现频率大于n/2，所以排序后的中间位置必然是众数

c++

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];  
    }
};

python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]  # // python 整除

摩尔投票法：

c++

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ret = 0;
        int counter = 0;
        for(auto num : nums){    // 遍历 vector 容器
            if(counter == 0){
                ret = num;
                counter = 1;
            }else if(ret == num){
                counter++;
            }else{
                counter--;
            }
        }

        return ret;
    }
};

python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counter = 0
        for i in nums:
            if counter == 0:
                ret = i
                counter = 1
            elif i == ret:
                counter += 1
            else:
                counter -= 1
        
        return ret