Boyer-Moore多数投票算法

Question

我最近开始学习Java，并且正在研究一些简单的算法。我找到了Boyer投票算法这里。

我正试图更好地为我的解决方案编写好的代码。请给我你的建议。

import java.util.Scanner;

public class MajorityVoteAlgorithm {

    public static void main(String[] args) {

        Scanner keyboard = new Scanner(System.in);
        int size = keyboard.nextInt(); // define size of array
        int[] array = new int[size];

        // initialize array
        for (int i = 0; i < array.length; i++) {
            array[i] = keyboard.nextInt();
        }

        majorityelement(array);

    }

    private static void majorityelement(int[] array) {
        int count = 0;
        int candidate = 0;
        for (int i = 0; i < array.length; i++) {
            if (count == 0) {
                candidate = array[i]; 
                // set the count as 1
                count = 1;
                continue;
            } else if (candidate == array[i])
                count++;
            else {
                count--;
            }
        }

        if (count == 0) {
            System.out.println("No majority element found");

        } else {
            // set the count to zero to count the occurrence of the candidate
            count = 0;
            for (int i = 0; i < array.length; i++) {
                if (candidate == array[i])
                    count++;
            }

            if (count > array.length / 2)
                System.out.println("Majority element is " + candidate);
            else
                System.out.println("No majority element found");
        }

    }
}

Answer 1

• int[]是一个很强的要求。代码不进行任何随机访问。考虑将参数从数组更改为流(这样可以处理不适合内存的数据)。
• 该方法执行两个(技术上)无关的工作:查找可能占主导地位的元素，并验证该元素确实占主导地位。我建议将它分成两种方法，原因如下：
  • 每个循环都有一个重要的工作，应该有一个名字。
  • 如果保证主要因素的存在，核查就是浪费时间。
  • 如果保证主要元素的存在，则可以将需求放宽到输入迭代器。

• 不要从算法中打印任何内容。让main处理结果。

Answer 2

有趣的算法。

实现似乎是正确的，正确地处理诸如空数组和带有一个元素的数组之类的角情况。

除此之外，您还应该始终如一地使用大括号，而不仅仅是在必要的地方。您当前的风格是极简主义的，不允许简单的可视化解析。

每当使用具有名称的算法时，请在函数描述或实现中的注释中写入名称。还包括一个链接，如果你可以，以节省某人的谷歌搜索。

Answer 3

添加到已经给定的输入，而不是运行循环计数，然后检查计数，处理角的情况-只有一个元素的数组首先。如果只有一个元素，就可以节省时间。