gpt4 book ai didi

algorithm - 计算子数组中的唯一值

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:12:21 26 4
gpt4 key购买 nike

数组 a*b 是给定的,其中包含最多 1e5 的数字,我们必须对每个 k*k 子数组中的唯一数字的计数求和,有 a-k*b-k 子数组例如

1 2 3 4 
3 2 4 1

对于 k=2子数组是

{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 并向相反方向移动。不担心内存使用,我只是在寻找一种更快地完成此操作的方法

最佳答案

a == b 是一个等价关系。给定一个元素集(你的子数组),你可以找到与你找到的方法的关系的等价类:

对于子数组 A 中的每个元素 x,您采用 c[x],它是一个 int(c 数组元素全部初始化为 0 ).如果这个 c[x] == 0 那么你有一个新的独特元素 c[x]++。否则你增加 c[x]

此算法与子数组中的元素数量线性(显然,您对每个子数组重复此过程并对结果求和以获得所需结果)。

但是时间复杂度不能再低了,因为无论如何你都需要检查每个元素。

关于algorithm - 计算子数组中的唯一值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46852306/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com