2

我试图编写一个算法，如果数组中存在多数元素，则返回 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;
}
4

3 回答 3

5

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

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

(1) 从数据中创建一个直方图：

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

O(n)如果您使用 aHashMap作为地图，这种方法是平均的。

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

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

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

编辑：

我误解了手头的问题，我以为您正在寻找是否存在唯一的最大值。这两个解决方案仍然适合该问题，您只需修改每个解决方案的最后一步 [检查最常出现的元素是否出现超过一半的时间，这在O(n)] 中再次相当容易和可行。

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

于 2012-04-14T14:23:28.797 回答
1

大小为 n 的数组 A[] 中的多数元素是出现超过 n/2 次的元素

public static boolean find(int[] arr, int size) { 
int count = 0, i, mElement;
for (i = 0; i < size; i++) {
    if (count == 0)
        mElement = arr[i];
    if (arr[i] == mElement) 
        count++;
    else
        count--;
}
count = 0;
for (i = 0; i < size; i++)
    if (arr[i] == mElement)
        count++;
if (count > size/2)
    return true;
return false;
}
于 2015-02-17T22:14:58.407 回答
0

以下是 O(n) 解决方案 Find Majority Element

于 2012-04-14T14:48:39.587 回答