计算子数组中的唯一值 [英] Count unique values in subarrays

问题描述

给出了数组 a * b ，其中包含不超过1e5的数字，我们必须对每个 k *中的唯一数字计数求和k 子数组，
有 ak * bk 子数组
例如

Array a*b is given, which contains numbers up to 1e5, and we have to sum the count of unique numbers in every k*k subarray, there are a-k*b-k subarrays e.g

1 2 3 4 
3 2 4 1

对于k = 2
个子数组

for k=2 subarrays are

{1,2,3,2}(3distinct values)
{2,3,2,4}(3distinct values)
{3,4,4,1}(3distinct values)

输出为9

有没有比使用表来存储实际所有发生次数的表更快的方法已处理的 k * k 子数组（例如，在索引3中，我们将3的计数存储在子数组中），移动了 k * k 窗口加1，并在右边增加值并从左边删除，如果递增后的值为1，则递增唯一数字计数器；如果减量后的值为0-减少唯一编号计数器。
到达该行的末尾后，向下走1并向相反的方向移动。
不用担心内存使用，我只是在寻找一种更快的方式

Is there a faster approach than using a table which stores count of every number ocurrencies in an actaully processed k*k subarray(e.g at index 3 we store count of 3's in a subarray), moving a k*k window by 1 and adding values from right and removing from left, if after incremention value is 1 - increment unique numbers counter; if after decrementation value is 0 - decrement unique numbers counter. After getting to the end of the row, go 1 down and move in the opposite direction. Not worried about memory usage,im just looking for a way to do this faster

推荐答案

a == b 是等价关系。
给定一个元素集（您的子数组），您可以使用找到的方法找到该关系的等价类：

a == b is an equivalence relation. Given A the set of elements (your subarray), you can find the equivalence classes of the relation with the method you found:

对于每个元素x子数组 A 取 c [x] 这是一个整数（ c 数组元素都初始化为0）。如果此 c [x] == 0 ，则您有一个新的唯一元素，因此 c [x] ++ 。否则，您增加 c [x] 。

For each element x in the subarray A you take c[x] which is an int (c array elements all initialized to 0). If this c[x] == 0 then you have a new unique element so c[x]++. Otherwise you increment c[x].

此算法对数字线性子数组中的元素数（显然，您需要为每个子数组迭代此过程，并对结果求和以获得所需的结果。）

This algorithm is linear to the number of elements in the subarray (obviously you iterate this process for each subarray and sum the results to get what you want).

但是时间复杂度不能降低，因为您仍然需要检查每个元素。

But time complexity can’t be lower, cause you need to check each element anyway.

这篇关于计算子数组中的唯一值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！