V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hyyy
V2EX  ›  程序员

如何判断一组数字中的重复次数和有无递增递减?

  •  
  •   hyyy · 2016-08-09 15:52:38 +08:00 · 2918 次点击
    这是一个创建于 3013 天前的主题,其中的信息可能已经有所发展或是发生改变。

    假如有一组数字:

    {1, 1, 1, 2, 3, 4}
    

    怎么去判断是否有重复次数大于 2 的重复数字(比如 1 ),有没有递增递减组合长度大于 2 的组合(比如 123 )。该用正则表达式判断还是其他方法呢?

    ###################################
    {1, 3, 5, 4, 1} --> 无重复数字和递增递减
    {1, 1, 1, 3, 5} --> 有重复数字但无递增递减
    {1, 3, 4, 5, 9} --> 无重复数据但有递增递减
    {1, 1, 1, 2, 3} --> 有重复数字和有递增递减
    ###################################
    
    9 条回复    2016-08-09 18:06:13 +08:00
    yalanaika
        1
    yalanaika  
       2016-08-09 15:58:56 +08:00
    看你要求优化时间还是空间,优化时间的话都有很方便的做法,第一问直接遍历一遍就好 第二问用最长增长子序列算法跑一下就好, https://en.wikipedia.org/wiki/Longest_increasing_subsequence
    a199261800
        2
    a199261800  
       2016-08-09 16:04:56 +08:00
    @yalanaika 搞过算法?最长增长子序列,好熟悉的字眼
    menc
        3
    menc  
       2016-08-09 16:07:29 +08:00
    @a199261800 本科基本知识
    wangxn
        4
    wangxn  
       2016-08-09 16:17:42 +08:00 via Android
    1 1 2 1 3 算不算有重复数字?算不算有递增序列?
    hyyy
        5
    hyyy  
    OP
       2016-08-09 17:06:44 +08:00
    @wangxn 算重复数字,但是不算递增序列。
    wangxn
        6
    wangxn  
       2016-08-09 17:12:17 +08:00 via Android
    @hyyy 那这个没必要用最长递增子序列了,直接一遍扫描就完成了。
    wander2008
        7
    wander2008  
       2016-08-09 17:46:30 +08:00 via iPhone
    leetcode 上有个题就是求自增序列的。去看看,
    messyidea
        8
    messyidea  
       2016-08-09 17:52:33 +08:00
    只要求找递增递减组合长度大于 2 ,为啥还要用最长增长子序列 - -
    neosfung
        9
    neosfung  
       2016-08-09 18:06:13 +08:00
    一个 map 保存出现次数,遍历的时候顺便判断和前面两个元素是否构成递增递减。
    如果这条是面试题,那还真的缺点水准
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2759 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 14:53 · PVG 22:53 · LAX 06:53 · JFK 09:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.