求优化，最后一个test case过不去!【FB Coding Puzzle】

找不重复值的一道题，求个思路，一定加米🙏

题目如下：


​我试了list，也试了用set，都是最后的testcase超时：

补充内容 (2021-08-30 09:12 +8:00):
  deque + set 过了，谢谢大家，code贴在下面了
其实最初也试了deque，因为可以O(1) popleft，但因为查找太慢没过
也试了list + set，因为可以O(1)查找，但因为pop(0)太慢没过
结果就没想到deque + set 🤦‍♀️

  eaten = deque([-1] * K) # FIFO
  types = set([-1])
  counter = 0
  
  for i in range(N):
    if D[i] not in types:
      counter += 1  # eat it
      old_type = eaten.popleft() # remove extra outdated history
      eaten.append(D[i])
      if old_type in types:
        types.remove(old_type)
      types.add(D[i])
      
  return counter

可以试试用个map存放被吃下去的dish，key是Di, value是i，然后遍历dish数组，如果Di不在map里或者map[Di]+k <= i，就可以吃掉，然后更新map[Di]
这样应该是O(n)复杂度

idealmaster 发表于 2021-08-29 00:00:03
可以试试用个map存放被吃下去的dish，key是Di, value是i，然后遍历dish数组，如果Di不在map里或者map+k <= i，就可以吃掉，然后更新map
这样应该是O(n)复杂度

谢谢～请问怎么更新map呢（删除掉最旧的一条记录）？

补充内容 (2021-08-29 15:06 +08:00):
可以直接O(1)删除hashmap最老的记录么

jl_tzc 发表于 2021-8-29 00:04
谢谢～请问怎么更新map呢（删除掉最旧的一条记录）？

补充内容 (2021-08-29 15:06 +08:00):

每个Di在map里最多只会有一条记录，如果map[Di]是在当前K size窗口里的，就什么也不做，如果在窗口外，直接更新map[Di] = i，另外cnt++就行了，O(1)操作
还有刚才才看到你的代码，问题主要是pop(0)，python list pop(0)是O(n)操作，n是list的长度，在这里相当于O(K)，最坏也就是O(n)，整体就变成了O(n^2)了，你可以尝试用collections.deque()取代list，然后用popleft()，但这其实没有必要，你不需要每次都记住哪些值被移出窗口外了，只需要检查当前值是不是在窗口里就行了，因为窗口里只能有一个特定dish

idealmaster 发表于 2021-8-29 15:00
可以试试用个map存放被吃下去的dish，key是Di, value是i，然后遍历dish数组，如果Di不在map里或者map[Di]+k ...

谢谢回复，不过如果是
k = 2
1 2 2 2 1
按照这个算法
第一个1吃掉, counter += 1:：map[1] = 0
第一个2吃掉, counter += 1：map[2] = 1
第二个2不吃
第三个2吃掉, counter += 1：因为3 - (map[2] = 1) = 2 = K
但好像这里还不应该吃呢，因为之前刚吃过1, 2

jl_tzc 发表于 2021-08-29 00:04:09
谢谢～请问怎么更新map呢（删除掉最旧的一条记录）？

补充内容 (2021-08-29 15:06 +08:00):

可以用Linkedlist + Map的方法，这样增删查找都是O(1). 就是维护代码有点烦，略了…

jl_tzc 发表于 2021-08-29 07:57:29
谢谢回复，不过如果是
k = 2
1 2 2 2 1

噢我理解错题意了，那就试试map[Di] = len(map)？记录的是前K个吃下去寿司的index，如果Di已经在map里，就先判断一下len(map)-K > map[Di]

我觉得可能有点想复杂了，这个题具体需要实现的是动态track previous K 个 dish. 因为说了不会吃相同type的dish，也相当于K个type. 实现动态track previous K个dish的最好方法就是用queue， 你可以用deque 也是double linked list来实现， 这样维护的成本（插入，删除）就能控制在O（1）。 但是有一个问题，就是在queue里面查找还是O（K）， 优化这点你可以同步记录一个set来记录queue里面的元素，这样查找也能优化为O（1）。

idealmaster 发表于 2021-8-29 10:20
噢我理解错题意了，那就试试map[Di] = len(map)？记录的是前K个吃下去寿司的index，如果Di已经在map里，就 ...

抱歉，刚才试着写了一下，应该是map[Di] = cnt，相当于看Di最近被更新的index是不是在已经吃下去的寿司中的最近K个index中间

1. def kaiten(A, k):
   
2.     idx = {}
   
3.     cnt = 0
   
4.     for x in A:
   
5.         if cnt-k >= idx.get(x,-k):
   
6.             cnt += 1
   
7.             idx[x] = cnt
   
8.     return cnt

复制代码

这题目不就是操作系统的cache吗，只不过当cache清除cache的策略是把最早的给请出cache罢了。
cache查询必须是O(1)，cache满了把最老的那个请出去也是O(1)。

这题目其实比LRU简单啊。毕竟LRU还涉及到更新cache中元素的最近访问时间这个信息。

常规操作的话，应该是 字典 加 链表，链表满了的话，比如达到K个元素了，下一次查询发现cache miss，就把最后一个元素删除，把新元素插入链表开头，同时更新字典。