美文网首页
Sliding Window 变形题vocation.

Sliding Window 变形题vocation.

作者: 98Future | 来源:发表于2017-11-02 14:10 被阅读0次

    这题可以理解为

    给定一个array, 可以有重复数字,问最小的length that covers all unique integers.

    比如说有[1,2,3,4,5] unique int

    array可以是[2,2,2,1,3,4,5,5]

    这样的话其实2,1,3,4,5 length 5可以搞定。

    我的做法是首先用Set filter选出总共几个unique的int。

    然后双指针,一个fast pointer, 一个slow pointer。

    然后用int[] arr来记录每个integer 在当前sliding window里出现了几次。

    我们只想让当前sliding里的number每个出现次数为1. 所以如果这个number出现次数超过1的话,把slow移到下一个出现次数为1次的同样这个number。每一轮我们都用fast-slow+1得到当前sliding window的size,看看这个有没有办法更短。

    我不确定我这个版本是不是完全 detect了所有edge case。。简单测试了一些case,但是由于那个平台不像leetcode给看test case 所以不是很确定。

    相关文章

      网友评论

          本文标题:Sliding Window 变形题vocation.

          本文链接:https://www.haomeiwen.com/subject/igvopxtx.html