算法| 多数元素

Question

我试图写一个算法,如果一个数组中存在多数元素则返回true,否则返回false.编辑:我只能判断两个元素是否相等.意思是我不能使用<或>,只有=.编辑:解决方案应采用分而治之的方法.它的运行时不应该超过nlogn,我在java中写了一些东西,但我不确定它是否正确以及如何计算运行时..这是我得到的:

public static boolean MajorityBoolean(int[] arr) {
    int c;
    int n = arr.length;
    for (int i = 0; i < n; i = i + 2) {
        System.out.println("*");
        if ((arr[i] == arr[(i + 1)%n]) || ((arr[i] == arr[(i - 1+n)%n]))) {
            c = 0;
            for (int j = 0; j < n; j = j + 1)
                if (arr[j] == arr[i])
                    c = c + 1;
            if (c > n / 2)
                return true;
        }
    }
    return false;
}

Answer 1

所描述的算法的运行时间是O(n^2).外循环执行n/2次数,因此内部计数器j被重置 n/2次数,因此内循环被执行总O(n^2)次数.

我不确定我是否遵循了你的想法背后的逻辑,但这里有两种方法我将如何实现它[在高级伪代码中]:

(1)从数据中创建直方图:

• 创建一个Map<Integer,Integer>[键是元素,值是出现次数]
• 迭代数组,并为每个元素计算它出现的次数
• 迭代直方图并查找是否存在唯一的最大值.
• 如果有 - 返回true,否则返回false.

O(n)如果您使用a HashMap作为地图,则此方法是平均值.

(2)排序并找到最大出现次数:

• 对数组进行排序 - 结果,所有相等的元素彼此相邻.您可以Arrays.sort(array)用于排序.
• 计算每个元素出现的次数[类似于直方图的想法],并查找是否存在唯一的最大值.您实际上不需要维护所有元素的数据,它足以维持前2个,最后看它们是否相同.

这个解决方案是O(nlogn)平均值+最差情况[实际上,取决于排序 - 合并sor t给你O(nlogn)最坏的情况,而快速排序给你O(n^2)最坏的情况,两者都是O(nlogn)平均情况].

编辑:

我误解了手头的问题,我以为你在寻找是否有一个独特的最大值.这两个解决方案仍然适用于这个问题,您只需要修改每个解决方案的最后一步[检查最常出现的元素是否出现超过一半的时间,这也是相当容易和可行的O(n)].

此外,还有另一种解决方案:使用选择算法查找中位数,找到后,检查它是否为多数元素,如果是,则返回.由于选择算法是基于分而治之的解决方案,我认为它符合您的需求.