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異常。