Leetcode169. 多数元素Every day a leetcode

90 阅读 0 评论 60 点赞

我是靠谱客的博主繁荣小鸭子，这篇文章主要介绍Leetcode169. 多数元素Every day a leetcode，现在分享给大家，希望可以做个参考。

Every day a leetcode

题目来源：169. 多数元素

解法1：hash

因为数组是非空的，并且给定的数组总是存在多数元素，所以hash表中的最大值对应的下标就是多数元素。

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> hash;
        int ans=0;
        int cnt=0;
        for(int i:nums)
        {
            hash[i]++;
            if(hash[i]>cnt)
            {
                ans=i;
                cnt=hash[i];
            }
        }
        return ans;
    }
};

结果：
在这里插入图片描述

解法2：排序

如果将数组 nums 中的所有元素排序，那么下标为 numsSize/2 的元素一定是多数元素。

代码：

复制代码

1
2
3
4
5
6
7
8
9
int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}
int majorityElement(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmpfunc);
    return nums[numsSize/2];
}

结果：
在这里插入图片描述

解法3：随机化

由于一个给定的下标对应的数字很有可能是众数，我们随机挑选一个下标，检查它是否是众数，如果是就返回，否则继续随机挑选。

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        while(1)
        {
            int randNum=nums[rand()%nums.size()];
            int count=0;
            for(int num:nums)
            {
                if(num == randNum) count++;

            }
            if(count>nums.size()/2) return randNum;
        }
    }
};

结果：
在这里插入图片描述

解法4：Boyer-Moore 投票算法

思路：
如果我们把众数记为 +1，把其他数记为 -1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

算法：
在这里插入图片描述

详情见：官方题解

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate=-1;
        int count=0;
        for (int num:nums)
        {
            if(num == candidate) count++;
            else if(--count<0)
            {
                candidate=num;
                count=1;
            }
        }
        return candidate;
    }
};