摩尔投票法

落日映苍穹つ 2023-07-02 09:24 23阅读 0赞

背景： 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;
        }
    }