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实现

&nbsp;LeetCode高频题目(100)汇总-Java实现&nbsp;&nbsp;&nbsp;【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洛谷

第N个泰波那契数

题源: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

【程序员赚钱思路】

&nbsp;程序员如果想赚大钱,只有两个路:&nbsp;1.不断接单;&nbsp;2.卖出产品。&nbsp;为了找工作刷题,现在搭配好:C++、算法导论和leetcode。其他的不要搞了。&nbsp;&nbsp;我现在决定了,要做就做好。要不然就不设置目标,继续搞我的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&lt;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