前往所有城市所需的最短天数窗口

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)，正如哈希映射平均提供的那样）