摩尔投票法-蒲公英云

摩尔投票法

背景： leetcode 169题求一个数组中，出现次数大于 n/2;的元素

如果在一个遍历中解决这个问题？？
答案就是摩尔投票法。

摩尔投票法：用一个计数器，每次当计数器为0时，以当前遍历元素为起点遍历，当往下遍历时，相同元素计数加1，元素不同计数器减1。那么最后剩下的元素为出现次数大于n/2。

eg: [2222221111];

public int majorityElement(int[] nums) {
    int candidate = nums[0], count = 1;
    for (int i = 1; i < nums.length; ++i) {
      if (count == 0) {
        candidate = nums[i];
        count = 1;
      } else if (nums[i] == candidate) {
        count++;
      } else{
        count--;
      }
    }
    return candidate;
  }

leetcode 229 求众数II ，找出当前出现次数大于 n/3.。
思路：在169题中，出现n/2只有一个元素，而在本题次数大于n/3.最多2个。于是拿两个计数去判断即可。（参考评论的^ ^）;

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int cx = 0,cy = 0;
        int x = 0,y = 0;
        for (int n: nums) 
        {
            if ((cx == 0 || n == x) && n != y) {
                cx++;
                x = n;
            } else if (cy == 0 || y == n) {
                cy++;
                y = n;
            } else {
                cx--;
                cy--;
            }
        }
        int count = 0;
        for (int n: nums) {
            if (x == n) count++;
        }
        if (count > nums.length/3) 
            res.add(x);
         count = 0;
        for (int n: nums) {
            if (y == n) count++;
        }
        if (count > nums.length/3 && x!= y)
            res.add(y);
        return res;
    }
}