时间戳

首页 > 解决方案 > 如何在窗口中获得不同的数字？

python - 如何在窗口中获得不同的数字？

问题描述

给定一个包含 N 个整数、A 1、A 2、... A N和一个整数 B 的数组。返回大小为 B 的所有窗口中不同数字的计数。

A=[1, 2, 1, 3, 4, 3]和B = 3。所有大小为 的窗口B，输出为：

 [1, 2, 1]
 [2, 1, 3]
 [1, 3, 4]
 [3, 4, 3]
 So, we return an array [2, 3, 3, 2].

代码如下

result = [len(set(A[i:i+B])) for i in range(len(A)-B+1)]

错误：

我得到了正确的输出，但是由于没有必要检查窗口中的每个计数，所以出现时间限制超出错误。我可以从右边添加每个数字并从左边删除吗？如何做到这一点？

标签： python

解决方案

您的脚本处理每个条目B时间。越大B，脚本的效率就越低。

如果您使用滑动窗口，则处理每个条目两次就足够了：

from collections import Counter    
def uniqueNumbersInWindow(A, B): 
    result = []
    slidingWindow = Counter(A[0:B])
    result.append(len(slidingWindow))
    for remove, add in zip(A, A[B:]):
        slidingWindow[remove] -= 1
        if (slidingWindow[remove] == 0):
             del slidingWindow[remove]
        slidingWindow[add] += 1
        result.append(len(slidingWindow))
    return result

基准

我将此和achy97 的解决方案与您的幼稚解决方案进行了基准测试：

len_a = 10_000_000
same = [7] * len_a
rand = random.choices(range(1000), k=len_a)
samples = 3
for f in ['socowi', 'achy97', 'op']:
    for b in [3, 1000]:
        for a in ['same', 'rand']:
            t = timeit.timeit(
                    f'{f}({a},{b})',
                    number=samples,
                    globals=globals()
                ) / samples
            print(f'| {f} | {a} | {b} | {t:.2f}s |')
解决方案 一种 乙 平均 时间
索科维 相同的 3 4.17s
索科维 兰特 3 8.51s
索科维 相同的 1000 4.63s
索科维 兰特 1000 7.20s
achy97 相同的 3 4.48s
achy97 兰特 3 6.32s
achy97 相同的 1000 4.68s
achy97 兰特 1000 6.11s
操作 相同的 3 2.68s
操作 兰特 3 2.92s
操作 相同的 1000 101.27s
操作 兰特 1000 186.67s

结果表明，滑动窗口解决方案的运行时间与B.

推荐阅读