6

文件 input.txt 由两行组成：第一行有整数 N 个空格，然后是整数 K (1 ≤ N,K ≤ 250000)。Second 有 N 个空格分隔的整数，其中每个整数都小于或等于 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 的误解？

4

2 回答 2

2

您的算法很好，但忽略了时间len(trees) < K，这是O(NK)因为每次调用minand maxis 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
于 2016-05-12T19:02:33.887 回答
1

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

移动 R，递增 Counts[A[1]]，如果更新零条目，则递减 Z，直到 Z 变为 0
此时子数组 [L..R] 包含从到 K 的所有值

现在移动 L，减少离开窗口的值的计数条目。如果某些条目变为 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
于 2016-05-12T18:51:12.840 回答