leetcode169——Majority Element （C++）

收录于 2022-05-05 05:27:06

查看 8002 次

Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.

You may assume that the array is non-empty and the majority element always exist in the array.

个人博客：http://www.cnblogs.com/wdfwolf3/。

题目比较好理解，在含有n个元素的数组中找出出现次数超过?n/2?的元素，假设数组不为空而且这个数是一定存在的。

1.moore-voting算法

这个算法就是为解决这个问题诞生的，主要思想就是找出一对不同的元素就去掉它们，最后剩下的一定是所找的元素。

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

(16ms)

2.hash

遍历数组，利用hash方式记录元素出现的次数，当某个元素次数超过?n/2?时，即为我们要找的。

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

(28ms)

3.sorting

对数组进行排序，由于要找的元素超过半数，所以下标n/2的元素一定是它，这里总数奇偶不影响，可以自己举例验证一下。

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

4.randomization

随机选取数组中的一个数，验证它是不是超过半数的数字。时间最快，有一半几率选中，当然最坏的情况比较糟糕，但这不重要，就像快速排序时间复杂度一样。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        srand(unsigned(time(NULL)));
        int tmp,i,count;
        while(true)
        {
            tmp=nums[rand()%nums.size()];
            for(i=0,count=0;i<nums.size();i++)
            {
                if(tmp==nums[i])
                    count++;
                if(count>nums.size()/2)
                    return tmp;
            }
        }
    }
};

(16ms)

5.bit manipulation

就是把数字都作为二进制处理，每个二进制位上的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;
    }
}

（40ms）

6.分治

处理这种问题都可以尝试下分治方法，这道题也可以不过感觉太麻烦，就不写了。

标签智能推荐：

LeetCode高频题目（100）汇总-Java实现

 LeetCode高频题目（100）汇总-Java实现   【Leetcode-easy-1】TwoSum【Leetcode-easy-2】AddTwoNumbers【Leetcode-easy-3】LongestSubstringWithoutRepeatingCharacters【Leetcode-easy-5】LongestPalindromicSub

C++ 前期准备

在线编译网站：http://www.dooccn.com/cpp/刷题：https://leetcode.com/https://leetcode-cn.com/

Index

Tableofcontents目录TableofcontentsOJ-Improvemyself,better.Leetcode洛谷OJ-Improvemyself,better.Leetcode洛谷

题源：leetcode链接：https://leetcode-cn.com/problems/n-th-tribonacci-number/最简单的动态规划1classSolution{2public:3inttribonacci(intn){4if(n==0)return0;5if(n==1)return1;6inta=0;7intb=1;8intc=1;9intd=1;10for(inti=2

【程序员赚钱思路】

 程序员如果想赚大钱，只有两个路： 1.不断接单； 2.卖出产品。 为了找工作刷题，现在搭配好:C++、算法导论和leetcode。其他的不要搞了。  我现在决定了，要做就做好。要不然就不设置目标，继续搞我的MALTABGUI（数学建模）和量化投资。

[LeetCode] 929. Unique Email Addresses 独特的邮件地址

r(charc:email){if(c=='.')continue;if(c=='+'||c=='@')break;name.push_back(c);}name+=email.substr(email.find('@'));st.insert(name);}returnst.size();}};Github同步地址:https://github.com/grandyang/leetcode/is

[LeetCode] 1189. Maximum Number of Balloons 气球的最大数量

t;for(charc:text)++charCnt[c];for(charc:balloon){if(c=='l'||c=='o')res=min(res,charCnt[c]/2);elseres=min(res,charCnt[c]);}returnres;}};Github同步地址:https://github.com/grandyang/leetcode/issues/1189参考资料：

单链表字符串判断回文

思路使用快慢两个指针找到链表中点，慢指针每次前进一步，快指针每次前进两步在慢指针前进的过程中，同时修改其next指针，使得链表前半部分反序。最后比较中点两侧的链表是否相等c版本代码见https://github.com/hkui/algo_practice/tree/master/c/linklist/palindrome_strjava版本https://github.com/andavid/l

剑指Offer-第8天动态规划（简单）

第一题题目链接：https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/个人题解：迭代即可，可以减少空间复杂度，只需要使用常数级别的空间即可。代码：constintmod=1e9+7;classSolution{public:intfib(intn){if(n<2)returnn;inta=0,b=0,c=1;for(inti=2;i&l

[LeetCode] 1051. Height Checker 身高检查器

[i]!=heights[i])++res;}returnres;}};Github同步地址:https://github.com/grandyang/leetcode/issues/1051参考资料：https://leetcode.com/problems/height-checker/https://leetcode.com/problems/height-checker/discuss/2