Java代码找出数组中出现次数大于三分之一次的数 - 摩尔投票算法详解

Java代码找出数组中出现次数大于三分之一次的数 - 摩尔投票算法详解

问题: 给定一个整数数组，找出数组中出现次数大于三分之一次的数。

解决方案: 我们可以使用摩尔投票算法来解决这个问题。该算法的思想是找到一个数，它在数组中出现的次数大于三分之一，即假设这个数为众数。在遍历数组时，如果当前数字与候选众数相同，则将计数器加1；否则，将计数器减1。如果计数器为0，则将候选众数替换为当前数字，并将计数器设为1。最后再遍历一遍数组，统计候选众数的出现次数，如果出现次数大于三分之一，那么这个数就是出现次数大于三分之一次的数。

**Java代码实现:**javapublic static void findMajorityElement(int[] nums) { 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) { System.out.println(candidate1); } if (count2 > nums.length / 3) { System.out.println(candidate2); }}

代码解释:

1. 初始化两个候选众数 candidate1 和 candidate2，以及它们的计数器 count1 和 count2。2. 遍历数组，对于每个数字 num： - 如果 num 等于 candidate1，则 count1 加1。 - 如果 num 等于 candidate2，则 count2 加1。 - 否则，如果 count1 为0，则将 candidate1 设置为 num，并将 count1 设置为1。 - 否则，如果 count2 为0，则将 candidate2 设置为 num，并将 count2 设置为1。 - 否则，将 count1 和 count2 减1。3. 再次遍历数组，统计 candidate1 和 candidate2 的出现次数。4. 如果 count1 大于数组长度的三分之一，则打印 candidate1。5. 如果 count2 大于数组长度的三分之一，则打印 candidate2。

时间复杂度: O(n)，因为我们遍历数组两次。空间复杂度: O(1)，因为我们只使用了常数个额外的变量。

总结:

摩尔投票算法是一种简单有效的算法，可以用于找出数组中出现次数大于三分之一次的数。该算法的时间复杂度为O(n)，空间复杂度为O(1)，非常高效。