什么是 n log(n) runtime 的解决方案，用于查找特定数字是否占据数组的一半以上

Question

一个程序的要求是打印一个数组中出现超过n/2次的数字。确保解决方案的算法具有 n log(n) 的运行时间。

[2, 1, 3, 2] = 无结果 [1, 5, 2, 5, 5] = 5

我目前的解决方案：

    int answer = -1;
    int[] a = {2, 4, 2, 5, 1};
    int[] occurances = {0, 0, 0, 0, 0, 0};

    for(int i = 0; i < a.length; i++){
        occurances[a[i]]++;
    }

    for(int i = 0; i < occurances.length; i++){
        if(occurances[i] > ((double)a.length)/2){
            answer = i;
        }
    }

    System.out.println(answer);

关于这个，我的解决方案的运行时间是多少？我不认为那是 n log(n) 因为它只通过数组一次。

如果不是 n log(n)，那么有 n log(n) 的解决方案是什么？如果是，为什么是n long(n)？

Answer 1

你的解取决于数组中的最大值，所以是伪多项式，即O(n + MAX)，其中MAX是最高的数组中的值。

查看是否有一个值占据数组的一半以上可以按照这个算法：

对数组进行排序
如果一个值占据数组的一半以上，它将占据排序数组的中间单元格（参见Pigeonhole principle）；取中间元素，并在下面的步骤中使用它
使用二分查找查找包含中间元素的范围的上下索引
比较中间元素上下索引的差值到数组长度的一半
如果索引差异大于一半长度，则中间元素被包含的时间超过一半；否则，答案是 "no".

另一种方法是在散列中使用计数 table:

构造一个散列 table，将元素映射到 O(n) 中的元素计数
遍历哈希 table，并在 O(n)

什么是 n log(n) runtime 的解决方案，用于查找特定数字是否占据数组的一半以上

What is a solution with n log(n) runtime for finding if a specific number occupies over half an array

java

big-o

runtime