找到包含所有数字的最小长度子数组

Question

文件input.txt由两行组成：第一行是整数N space然后是整数K（1 ≤N,K≤ 250000）。 Second有N个space分隔的整数，其中每个整数小于等于K。保证1到K的每个整数都在数组中。任务是找到包含所有整数的最小长度的子数组。并打印它的开始和结束。请注意，索引从 1.

开始

示例：

Input         Output
5 3           2 4
1 2 1 3 2

6 4           2 6
2 4 2 3 3 1

我在最近的编程竞赛中有这个任务。结束了，我没有作弊。我已经使用 python 3:

实现了它

with open('input.txt') as file:
    N, K = [int(x) for x in file.readline().split()]
    alley = [int(x) for x in file.readline().split()]

trees = {}
min_idx = (1, N)
min_length = N
for i in range(N):
    trees[alley[i]] = i
    if len(trees) == K:
        idx = (min(trees.values())+1, max(trees.values())+1)
        length = idx[1] - idx[0] + 1
        if length < min_length:
            min_idx = idx
            min_length = length
        if min_length == K:
            break


print (str(min_idx[0]) + " " + str(min_idx[1]))

想法是将第 i 棵树的最后位置保存到字典中，如果字典包含所有项目，则检查此子数组是否最小。

第 16 次测试表明我的算法超过了时间限制，即 1 秒。我认为，我的算法是 O(N)，因为它在整个数组中以一个运行完成，并且映射访问成本为 O(1).

如何加快这一算法？可以降低复杂性还是我误解了一些Python需要很多时间？

Answer 1

创建整数数组 Counts[K]，用零填充。
保留一些变量 - 左索引 L，右索引 R（比如你的 idx[0] 和 idx[1]），零计数 Z.
将 L 和 R 设置为 1，增加 Counts[A[1]]，将 Z 设置为 K-1

移动 R，递增计数[A[1]]，如果更新了零项则递减 Z，直到 Z 变为 0
此时子数组 [L..R] 包含从到 K

的所有值

现在移动 L，递减离开 window 的值的计数条目。 如果某个条目变为 0，则增加 Z。当Z变为非零时，停止移动L并再次移动R。

当R到达N，L停止时，流程结束。最小长度是有效 (R-L+1) 对中的最小值

Example run for your [1 2 1 3 2]

Move R
1 0 0  Z=2
1 1 0  Z=1
2 1 0  Z=1
2 1 1  Z=0
Move L
1 1 1  Z=0
1 0 1  Z=1 Stop moving L, check previous L,R pair 2,4
Move R
1 1 1  Z=0
move L
9 1 1  Z=1 Stop moving L, check previous L,R pair 3,5

Answer 2

你的算法很好但是忽略了 len(trees) < K 的时间，它是 O(NK) 因为每次调用 min 和 max 都是 O(K)。没有必要调用 max 因为 max(trees.values()) == i。处理 min 比较棘手，但如果您跟踪哪个键对应于最小索引，那么您可以仅在更新该键时重新计算它。

一个小问题是您的最后一个 if 并不总是需要检查。

总体：

trees = {}
min_idx = (1, N)
min_length = N
first_index = -1
for i in range(N):
    trees[alley[i]] = i
    if len(trees) == K:
        if first_index == -1 or alley[first_index] == alley[i]:
            first_index = min(trees.values())
        idx = (first_index+1, i+1)
        length = idx[1] - idx[0] + 1
        if length < min_length:
            min_idx = idx
            min_length = length
            if min_length == K:
                break

找到包含所有数字的最小长度子数组

find minimum-length subarray that has all numbers

python

arrays

algorithm

sub-array