Leetcode No.169 Majority Element(c++实现)

Leetcode No.169 Majority Element(c++实现)

1. 题目

1.1 英文题目

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

1.2 中文题目

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

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

1.3输入输出

输入 输出
nums = [3,2,3] 3
nums = [2,2,1,1,1,2,2] 2

1.4 约束条件

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -231 <= nums[i] <= 231 – 1

2. 分析

2.1 Moore”s voting

每次都找出一对不同的元素,从数组中删掉,直到数组为空或只有一种元素。 不难证明,如果存在元素e出现频率超过半数,那么数组中最后剩下的就只有e。代码如下:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
		// 摩尔投票法
        int candidate = nums[0]; // 候选值
        for (unsigned int i = 1, count = 1; i < nums.size(); i++)
        {
            if (count == 0) candidate = nums[i];
            count += (count == 0 || candidate == nums[i]) ? 1 : -1;
        }
        return candidate;
    }
};

参考自:https://blog.csdn.net/huanghanqian/article/details/74188349

2.2 哈希表法

建立一个哈希表,存储元素与其出现次数;遍历给定的数组,增加其哈希表中对应的次数;如果有一个次数大于长度/2,记录答案。代码如下:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
		// 哈希表法
        unordered_map<int, int> hash;
        int ans;
        int length = nums.size();
        for (int i = 0; i < length; i++)
        {
            hash[nums[i]]++;
            if (hash[nums[i]] > length / 2)
            {
                ans = nums[i];
                break;
            }  
        }
        return ans;
    }
};

参考自:https://blog.csdn.net/weixin_44176696/article/details/104445717

2.3 位操作法

把数字都作为二进制处理,每个二进制位上的n个bit相加看是否大于n/2,大于的话这一位上是1,小于的话就是0,把32位都这么处理完即可。具体代码如下:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int i,j,count,major=0;
        for(i=0;i<32;i++)
        {
            for(j=0,count=0;j<nums.size();j++)
            {
                if((nums[j]>>i&1)==1)
                    count++;
            }
            if(count>nums.size()/2)
                major+=(1<<i);
        }
        return major;
    }
};

参考自:https://www.cnblogs.com/wdfwolf3/p/5490887.html
位操作解读:https://www.cnblogs.com/zhoug2020/p/4978822.html

hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » Leetcode No.169 Majority Element(c++实现)