摩尔投票算法（Moore's Voting Algorithm）Java实现

摩尔投票算法是一种高效的算法，用于在数组中寻找出现次数超过一半或特定比例的元素。以下是摩尔投票算法的Java实现及其详细解析。

基础版：寻找出现次数超过一半的元素

java
public class MajorityElement {
    public static int findMajorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (candidate == num) {
                count++;
            } else {
                count--;
            }
        }
        
        // 验证候选元素是否确实超过半数
        count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }
        
        return count > nums.length / 2 ? candidate : -1; // 返回-1表示没有多数元素
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 3, 3, 4, 3, 5, 3};
        int majorityElement = findMajorityElement(nums);
        System.out.println("出现次数超过一半的元素是：" + majorityElement);
    }
}

算法解析

1. 初始化：设置候选元素candidate和计数器count为0
2. 遍历数组：
   • 当count为0时，将当前元素设为候选元素
   • 当前元素等于候选元素时，count加1
   • 当前元素不等于候选元素时，count减1
3. 验证阶段：再次遍历数组，统计候选元素的实际出现次数，确认是否超过半数

该算法时间复杂度为O(n)，空间复杂度为O(1)

进阶版：寻找出现次数超过n/3的元素

java
import java.util.ArrayList;
import java.util.List;

public class MajorityElementII {
    public static List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        int candidate1 = 0, candidate2 = 0;
        int count1 = 0, count2 = 0;
        
        // 第一轮遍历找出两个候选元素
        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        
        // 第二轮遍历验证候选元素
        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            }
        }
        
        if (count1 > nums.length / 3) {
            result.add(candidate1);
        }
        if (count2 > nums.length / 3 && candidate1 != candidate2) {
            result.add(candidate2);
        }
        
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 3, 3, 2, 2, 2};
        List<Integer> majorityElements = majorityElement(nums);
        System.out.println("出现次数超过n/3的元素是：" + majorityElements);
    }
}

算法解析

1. 初始化：设置两个候选元素candidate1、candidate2和对应的计数器count1、count2
2. 遍历数组：
   • 当前元素等于任一候选元素时，对应计数器加1
   • 当任一计数器为0时，将当前元素设为对应候选元素
   • 否则，两个计数器都减1
3. 验证阶段：统计两个候选元素的实际出现次数，确认是否超过n/3

该算法同样保持O(n)时间复杂度和O(1)空间复杂度

算法特点

1. 高效性：只需1-2次线性遍历，无需额外数据结构
2. 空间优化：仅使用常数空间
3. 应用场景：
   • 选举系统统计
   • 数据分析中的频繁项挖掘
   • 流数据处理

注意事项

1. 基础版算法假设数组中一定存在多数元素，否则需要验证阶段
2. 进阶版最多可能返回2个结果（因为超过n/3的元素最多两个）
3. 对于流式数据，算法同样适用，因为只需一次遍历

摩尔投票算法因其简洁高效的特点，成为解决多数元素问题的首选方案。