查找具有所有数字的最小长度子数组 [英] find minimum-length subarray that has all numbers

问题描述

文件input.txt由两行组成：首先是整数N，然后是整数K（1K≤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实现了它：

I had this task in a recent programming competition. It is over, and I am not cheating. I've implemented it using 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棵树放入字典中，如果字典中包含所有项，请检查此子数组是否最小。

The idea is to save last position of i-th tree into a dictionary and if dictionary contains all items, check if this subarray is minimum.

第16次测试表明我的算法超出了时间限制，即1第二。我认为我的算法是O（N），因为它一次完成一次跨阵列运行，并且地图访问成本为O（1）。

16th test showed that my algorithm exceeded time limit, which was 1 second. I think, that my algorithm is O(N), because it finishes in one run across array, and map access costs O(1).

如何提高速度这个算法？可以降低复杂性吗？还是我对一些需要很多时间的Python的误解？

How can one speed up this algorithm? Can be complexity reduced or is it my misunderstanding of some Python which takes much time?

推荐答案

您的算法不错，但是忽略了时间 len（trees）< K ，它是 O（NK），因为每次调用 min 和 max 为 O（K）。无需调用 max ，因为 max（trees.values（））== i 。处理 min 比较棘手，但是如果跟踪哪个键对应最小索引，则只有在更新该键时才能重新计算它。

Your algorithm is good but ignoring the time that len(trees) < K, it's O(NK) because every call to min and max is O(K). There's no need to call max because max(trees.values()) == i. Dealing with min is trickier, but if you keep track of which key corresponds to the minimum index then you can recalculate it only when that key is updated.

次要点是您上一次的 不一定总是需要检查。

A minor point is that your last if doesn't always need to be checked.

总体：

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

这篇关于查找具有所有数字的最小长度子数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！