Java Program to Find an Index of an Array Such That Its Value Occurs at More Than Half of Indices in The Array

问题陈述

当前的任务是在一个 数组中找到一个索引，该索引处的值在数组索引的一半以上出现。这个数字通常被称为数组的众数。

如果一个元素出现的次数超过 n/2 次（其中 n 是数组的长度），则该元素被认为是数组的众数。如果存在这样的元素，则返回一个出现该元素的索引；否则，如果不存在众数，则返回 -1。

示例

输入

输出

 
0   

解释

数组元素 2 在 6 个索引中有 4 个出现。由于 4 > 6/2（即 3），所以 2 是众数。该函数应返回 2 的任何一个索引。在这种情况下，索引 0 是一个有效的答案。其他有效答案可能是 2、3 或 5。

解决方案方法

Boyer-Moore 投票算法是一种最优解决方案，时间复杂度为 O(n)，空间复杂度为 O(1)。该算法基于以下观察：

1. 候选者选择：如果我们抵消一对不同的元素中的每一个出现，就有可能找到众数。在这些抵消中幸存下来的元素就是众数。
2. 验证：在确定了候选者之后，我们需要通过计算其出现次数来验证它是否确实是众数。

输出

 
Index of majority element: 0   

解释

提供的 Java 代码有效地查找了数组中一个值的索引，该值是众数，意味着它在数组中出现的次数超过一半。`findMajorityElementIndex` 方法作为主要的 函数，并调用两个辅助方法：`findCandidate` 和 `isMajority`。

`findCandidate` 方法使用 Boyer-Moore 投票算法，通过遍历数组并调整候选者及其计数来选择潜在的众数。如果当前计数为零，则设置新的候选者；否则，根据当前元素是否与候选者匹配来增加或减少计数。

一旦确定了候选者，`isMajority` 方法就通过计算其在数组中的出现次数来验证该候选者是否真的是众数。如果候选者的计数超过数组长度的一半，则确认其为众数，`findMajorityElementIndex` 方法将返回该候选者的第一个索引。

如果不存在众数，则返回 -1。此方法效果最佳，确保了对大型数组的高效性能，其时间复杂度为 O(n)，空间复杂度为 O(1)。

结论

上面的代码提供了一种有效的方法，利用 Boyer-Moore 投票算法来发现数组中出现次数超过一半的数组元素的索引；该解决方案以 O(n) 的时间复杂度和 O(1) 的空间复杂度运行，使其非常适合此应用。