java - 具有 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 principle )；获取中间元素，并在下面的步骤中使用它
• 使用二分查找查找包含中间元素的范围的下索引和上索引
• 比较中间元素上下索引的差值与数组长度的一半
• 如果索引差异超过长度的一半，则包含中间元素的次数超过一半；否则，答案就是“否”。

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

• 构造一个哈希表，将一个元素映射到 O(n) 的元素计数
• 遍历哈希表，并在 O(n) 内获取最高计数