什么是具有 n log(n) 运行时的解决方案，用于查找特定数字是否占用了半个以上的数组

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原理);取中间元素，并在下面的步骤中使用它
• 使用二叉搜索查找包含中间元素的范围的下索引和上索引
• 将中间元素的上索引和下索引之间的差异与数组长度的一半进行比较
• 如果索引差值超过长度的一半，则中间元素包含的时间超过一半;否则，答案为"否"。

另一种选择是在哈希表中使用计数：

• 构造一个哈希表，该表将元素映射到 O(n) 中的元素计数
• 遍历哈希表，并以 O(n) 为单位获取最高计数