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

2016-08-09 15:52:38 +08:00
 hyyy

假如有一组数字:

{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} --> 有重复数字和有递增递减
###################################
2929 次点击
所在节点    程序员
9 条回复
yalanaika
2016-08-09 15:58:56 +08:00
看你要求优化时间还是空间,优化时间的话都有很方便的做法,第一问直接遍历一遍就好 第二问用最长增长子序列算法跑一下就好, https://en.wikipedia.org/wiki/Longest_increasing_subsequence
a199261800
2016-08-09 16:04:56 +08:00
@yalanaika 搞过算法?最长增长子序列,好熟悉的字眼
menc
2016-08-09 16:07:29 +08:00
@a199261800 本科基本知识
wangxn
2016-08-09 16:17:42 +08:00
1 1 2 1 3 算不算有重复数字?算不算有递增序列?
hyyy
2016-08-09 17:06:44 +08:00
@wangxn 算重复数字,但是不算递增序列。
wangxn
2016-08-09 17:12:17 +08:00
@hyyy 那这个没必要用最长递增子序列了,直接一遍扫描就完成了。
wander2008
2016-08-09 17:46:30 +08:00
leetcode 上有个题就是求自增序列的。去看看,
messyidea
2016-08-09 17:52:33 +08:00
只要求找递增递减组合长度大于 2 ,为啥还要用最长增长子序列 - -
neosfung
2016-08-09 18:06:13 +08:00
一个 map 保存出现次数,遍历的时候顺便判断和前面两个元素是否构成递增递减。
如果这条是面试题,那还真的缺点水准

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/298139

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX