如果一个数字出现超过或等于 N/4 次(N 是数组的长度)，则该数字很受欢迎。他希望我利用数组的排序属性，并提出比 O( 更好的解决方案n) 时间复杂度。
最佳答案
我会使用与二分搜索类似的方法来完成此操作。
首先我会找到 8 个数字的值，它们位于数组的 0/8、1/8、2/8 ... 8/8 上。当您对某些内容进行二分搜索时，您首先找到的数字与您首先找到的数字相同。
由于相同的数字必须在数组大小的 n/4 或更大范围内，因此它必须至少到达行中的两个边界。 2/8 和 3/8 处的数字相同。
因此，数字和部分位置的识别是在恒定时间内完成的。
然后你就继续查找它的起点和终点，这是典型的二分查找。
复杂度:O(log n)
关于arrays - 采访问题: How to find the most popular number in a sorted array，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29890902/