leetcode169. 多数元素的四种解法

leetcode169. 多数元素

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

1.哈希

class Solution {public:    int majorityElement(vector& nums) {        int count = nums.size()/2; //获取数组大小的一半        unordered_map hashTable; //        for(int i = 0; i  count){                return nums[i];            }        }        return 0;    }};

hash代码简化版

class Solution {public:    int majorityElement(vector& nums) {        unordered_map  mp;        for(int n:nums)               if(++ mp[n] > nums.size()/2)   return n;                 return -1;    }};

2.Moore投票(最优解)

摩尔投票法，投我++，不投–，超过一半以上的人投我，那我稳赢哇

class Solution {public:    int majorityElement(vector& nums) {        int candidate = 0, votes = 0;        for(int n : nums)        {            if(votes == 0)  candidate = n;              if(n == candidate)  ++votes;            if(n != candidate)  --votes;        }        return candidate;    }};

3.排序

class Solution {public:    int majorityElement(vector& nums) {        sort(nums.begin(), nums.end());        return nums[nums.size() / 2];               //因为出现频率大于n/2，所以排序后的中间位置必然是众数    }};

4.位运算

class Solution {public:    int majorityElement(vector& nums) {    int res = 0;    for(int i = 0 ; i > i) & 1;              //位运算法统计每个位置上1出现的次数，每次出现则ones+1        res += (ones > nums.size()/2)