所有城市旅行所需的最短时间窗口

Question

这是我在一次编码挑战中遇到的一个有趣的问题：

有k个城市和n天。旅行社会在第n天告诉你城市k。你应该找出你可以游览所有城市的最少天数。你也可以多次访问城市，但理想情况下，你不想这样做，因为你想尽量减少天数。在

输入：给你一个日期和城市的数组，其中天是指数，城市是值。 A=[7,4,7,3,4,1,7]所以A[0]=7意味着旅行社将在第0天向您显示城市7，第1天显示城市4，等等

所以在这里，如果你从第0天开始，你将在第5天游览所有城市，但你也可以从第2天开始，到第5天结束。在

输出：4因为您花了4天时间访问所有城市至少一次

我的解决方案：我有一个O（N^2）的解决方案，可以尝试城市的所有组合。但是测试表明，理想的时间和空间复杂性应该是O（N）。我该怎么做？在

def findmin(A):
    hashtable1={}
    locationcount=0
    #get the number of unique locations
    for x in A:
        if A[x] not in hashtable1:
            locationcount+=1

    index1=0
    daycount=sys.maxint
    hashtable2={}
    #brute force
    while index1<len(A):
        index2=index1
        prevday=index2
        ans=0
        count1=0
        while index2<len(A):
            if A[index2] not in hashtable2:
                count1+=1
                ans+=(index2-prevday)
                hashtable2[A[index2]]=1
            index2+=1
        if count1==count:
            daycount=min(ans,daycount)
        hashtable2.clear()
        index1+=1
    return daycount+1

Answer 1

这个问题可以用双指针方法来解决。在

某些数据结构应包含当前窗口中的元素计数。也许你的哈希表是合适的。在

将左右指针设置为列表的开头。在

向右移动指针，增加如下元素的表项：

  hashtable2[A[rightindex]] = hashtable2[A[rightindex]] + 1

当所有（locationcount）表项变为非零时，停止右指针移动。你有覆盖所有城市的左右间隔。记住间隔长度。在

现在向左移动指针，减少表项。当某个表项变为零时，停止移动左指针。在

再次移动右指针。重复上述步骤，直到列表结束。在

注意，索引只运行一次列表，复杂度是线性的（如果表条目更新是O（1），就像hash map提供的平均值一样）