leetcode [229]Majority Element II

佚名 7年前 (2019-05-06) 随笔 1565人围观抢沙发百度已收录

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋times.

Note: The algorithm should run in linear time and in O(1) space.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

题目大意：

求出数组中出现次数超过数组长度三分之一的数字。

解法：

采用摩尔投票算法，最基本的摩尔投票问题，找出一组数字序列中出现次数大于总数1/2的数字（并且假设这个数字一定存在）。显然这个数字只可能有一个。摩尔投票算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。摩尔投票算法也可以找众数，这里出现次数大于总数的1/3的数字，这个数字显然最多只有两个，先选出两个候选人A,B,遍历数组，如果投A（等于A），则A的票数++;如果投B，B的票数++；如果A,B都不投（即与A，B都不相等）,那么检查此时是否AB中候选人的票数是否为0，如果为0,则成为新的候选人；如果A,B两个人的票数都不为0，那么A,B两个候选人的票数均--；遍历结束后选出两个候选人，但是这两个候选人是否满足>n/3，还需要再遍历一遍数组，找出两个候选人的具体票数。

java:

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int major1=0,major2=1,cnt1=0,cnt2=0;
        List<Integer>res=new ArrayList<>();
        for (int i=0;i<nums.length;i++){
            if (nums[i]==major1) cnt1++;
            else if (nums[i]==major2) cnt2++;
            else if (cnt1==0){
                major1=nums[i];
                cnt1=1;
            }else if (cnt2==0){
                major2=nums[i];
                cnt2=1;
            }else{
                cnt1--;
                cnt2--;
            }
        }

        cnt1=cnt2=0;
        for (int i=0;i<nums.length;i++){
            if (nums[i]==major1) cnt1++;
            if (nums[i]==major2) cnt2++;
        }

        if (cnt1>nums.length/3) res.add(major1);
        if (cnt2>nums.length/3) res.add(major2);

        return res;
    }
}