查找列表中出现次数最多的数字范围
查找列表中出现次数最多的数字范围
提问于 2021-03-14 00:51:07
我必须遵循的复杂度是o(n)，所以我不允许使用嵌套循环。我大概知道我想做什么，但是我不确定如何存储范围的下限。目标是找到包含最多元素的区间的下界。我们将L表示为范围的长度。我试过的是：
lst = [1,2,3,4,5,5,6,6,6,12] #after sorting by radix
L = 3
for i in range(len(lst)):
lower_bound[i] = i
upper_bound[i] = i + L #in this case L = 3.
#if i is in range of certain i and its upper_bound,
#increment count for that interval
# e.g. 1 is in range of 0-3, so count for lower_bound[1] will +1.
# e.g. 6 is in range of 4-6, so count for lower_bound[4] will +3.
#return the lower_bound with max count 因此，对于本例，将返回3，因为3-6有7个元素(按最小下限排序)。我不确定这是否是正确的方法:(考虑到复杂度是o(n)，这看起来正确吗？
回答 1
Stack Overflow用户
发布于 2021-03-14 01:59:21
如果我正确理解你的问题，也许可以用两个指针的方法来解决。
将左指针(索引)设置为0，然后向右移动索引，直到lst[right]和lst[left]之间的元素差异大于L。
记住索引差异right - left
向左移动索引，直到元素差异小于L
再次向右移动索引，比较新的索引与当前索引的差异，得到最大值。
重复该操作，直到列表结束
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/66616115
复制相关文章
相似问题
腾讯云开发者
