K排序的块范围查询

Question

给定N个数字列表（1索引），如果一个连续块具有多于K个连续出现的相同元素，则为K排序块。

示例：[2,4,4,5,5,5,3,3]具有索引4至6的3阶块和7至8的2阶块。 4至6也是2阶块。

现在，如果我们给出形式查询：LeftIndex，RightIndex，令-K

我们需要LeftIndex和RightIndex之间要告诉很多订单-K块怎么都存在。

说，如果查询是2,8,2型，然后回答是3的3块与订单2.他们是从指数2至3,4至6,7至8

如何解决这个问题，如果查询高达100000，并且列表可以是100000.

Answer 1

你应该显示你所做的和你的想法。请参阅tour

包括有关您尝试过的内容以及您正在尝试执行的操作的详细信息。

算法很简单。

用i = leftIdx - 1开始一个循环，跳过并计算所有下一个等于list[i]的元素（使用while()循环）。如果相同元素的数量（包括list[i]）大于或等于K，则会找到一个新的Order-K块。现在更新i至i+count，并继续循环直至i > rightIdx。

只是要小心与角落的情况下（空列表，右Idd < = leftIdx等）和IndexOutOfBound异常。