在log（n）时间中找到已排序数组中至少出现k次的元素 [英] Find an element that occurs at least k times in a sorted array in log(n) time

问题描述

给定一个由n个元素和一个数字k组成的排序数组，是否有可能找到以log（n）时间出现k次以上的元素？如果出现的次数超过k次，则任何一个都可以接受。

Given a sorted array of n elements and a number k, is it possible to find an element that occurs more than k times, in log(n) time? If there is more than one number that occurs more than k times, any of them are acceptable.

如果是，怎么办？

编辑：
我能够在线性时间内解决问题，很高兴在此处发布该解决方案-但是在n中解决它相当简单。但是，我完全无法解决要在log（n）中工作的问题，这就是我的问题。

I'm able to solve the problem in linear time, and I'm happy to post that solution here - but it's fairly straightforward to solve it in n. I'm completely stumped when it comes to making it work in log(n), though, and that's what my question is about.

推荐答案

这里是 O（n / k log（k））解决方案：

i = 0
while i+k-1 < n: //don't get out of bounds
   if arr[i] == arr[i+k-1]:
       produce arr[i] as dupe
       i = min { j | arr[j] > arr[i] } //binary search
   else:
       c = min { j | arr[j] == arr[i+k-1] } //binary search
       i = c

这个想法是，如果索引 i + k-1 的元素与索引 i -很好，是骗子。否则，您无需检查 i 到 i + k-1 之间的所有元素。与 arr [i + k-1] 的值相同。

The idea is, you check the element at index i+k-1, if it matches the element at index i - good, it's a dupe. Otherwise, you don't need to check all the element between i to i+k-1, only the one with the same value as arr[i+k-1].

您确实需要回顾一下该元素的最早索引，但是可以保证超过 i + k 进行下一次迭代，使该算法的迭代总数为 O（n / k），每个算法取 O（logk）时间。

You do need to look back for for the earliest index of this element, but you are guaranteed to exceed the index i+k by next iteration, making the total number of iteration of this algorithm O(n/k), each takes O(logk) time.

这在渐近性上优于线性时间算法，尤其是对于 k （对于 k 在 O中的情况，算法衰减到 O（logn） （n），例如-查找至少以频率0.1重复的元素）

This is asymptotically better than linear time algorithm, especially for large values of k (where the algorithm decays to O(logn) for cases where k is in O(n), like for example - find element that repeats at least with frequency 0.1)

这篇关于在log（n）时间中找到已排序数组中至少出现k次的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！