Every day a leetcode

题目来源：169. 多数元素

解法1：hash

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

代码：

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 的元素一定是多数元素。

代码：

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：随机化

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

代码：

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，从结果本身我们可以看出众数比其他数多。

算法：

详情见：官方题解

代码：

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;
    }
};

结果：

解法5：分治

详情见：官方题解

最后

以上就是繁荣小鸭子为你收集整理的Leetcode169. 多数元素Every day a leetcode的全部内容，希望文章能够帮你解决Leetcode169. 多数元素Every day a leetcode所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。