作者suhang (suhang)
看板Python
标题[问题]算法 k distinct letters
时间Tue Mar 13 07:10:36 2018
https://imgur.com/a/2GAU3
my solution
https://repl.it/@shih_hsuanhsu/KDistinctCharacter
def KDistinctCharacter3
def KDistinctCharacter2
两个方法应该都正确，但是复杂度为O(nk)
网路上高手说可以做到O(n)
我试着又写了 KDistinctCharacter
但是我想不透该怎麽做
求助!
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 172.89.32.145
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Python/M.1520896240.A.EE7.html
1F：→ djshen: 想想看iterate的时候哪些东西可以不用重算 03/13 10:00
2F：推 Jeffrey11061: 大概就是不用每个run都检查window中的character 03/19 13:39
3F：→ Jeffrey11061: 用记录该字元上次出现的位置来达到O(n) 03/19 13:40